Submission

Score: 0

User: preum101

Problemset: Tech Sprites

Language: cpp

Time: 1.185 second

Submitted On: 2026-03-25 19:43:56

#include <bits/stdc++.h>
using namespace std;

signed main() {
    int n,m,t,tt;
    cin >> n >> m;

    long long va;
    long long val[n+1];
    for (int i = 0; i<n; i++) {
        cin >> va >> tt;
        va*=1000000000LL;
        ///va*=100LL;
        va+=tt;
        val[i+1] = va;
    }

    int a,b;
    int loc[n+1];
    memset(loc,-1,sizeof(loc));
    //cout << "L20 \n";
    int house = 0;
    for (int i = 0; i<m; i++) {
        cin >> a >> b;
        if (loc[a]==-1 && loc[b]==-1) {
            loc[a] = house;
            loc[b] = house;
            house++;
        } else {
            int la = max(loc[a],loc[b]);
            loc[a] = la;
            loc[b] = la;
        }
    }
    //cout << "HOUSE = " << house << "\n";
    for (int i = 1; i<n+1; i++) {
        if (loc[i]==-1) {
            loc[i] = house;
            house++;
        }
    }
    //cout << "HOUSE = " << house << "\n";
    //cout << "L34 \n";
    long long mn[house+1];
    long long mx[house+1];
    memset(mn,-1,sizeof(mn));
    //cout<<sizeof (long long)<<"L\n";
    memset(mx,-1,sizeof(mx)); //cout << sizeof(mn) << ' ' << sizeof(mx) << "L38 \n";
    for (int i = 1; i<=n; i++) {
        //cout << i << " " << loc[i] << " " << val[i];
        if (mx[loc[i]]==-1) {
            mx[loc[i]]=val[i];
        }
        if (mn[loc[i]]==-1) {
            mn[loc[i]]=val[i];
        }
        //cout << "L47 \n";
        mn[loc[i]] = min(mn[loc[i]],val[i]);
        mx[loc[i]] = max(mx[loc[i]],val[i]);
    }
    //cout << "\nL50 \n";
    vector<pair<long long,long long>> mm(house);
    for (int i = 0; i<house; i++) {
        //cout << i << ' ' << mn[i] << ' ' << mx[i] << '\n';
        mm.push_back(make_pair(mn[i],mx[i]));
    }

    sort(mm.begin(),mm.end());

    int c = 0;
    int i = 0;
    long long occ = 0;
    for (auto [x,y] : mm) {
        //cout << i << ' ' << x << ' ' << y << ' ' << occ << '\n';
        if (y<occ) {
            c++;
        } else {
            occ = y;
        }
        i++;
    }

    cout << c;
}