Submission

Score: 0

User: preum101

Problemset: Tech Sprites

Language: cpp

Time: 2.592 second

Submitted On: 2026-03-25 20:46:31

#include <bits/stdc++.h>
using namespace std;
#define int long long
long long val[1000001];
long long loc[1000001];
long long mn[1000001];
long long mx[1000001];
int aa[3000001];
int bb[3000001];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m,t,tt;
    cin >> n >> m;

    long long va;

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

    memset(loc,-1,sizeof(loc));
    //cout << "L20 \n";
    int house = 0;
    int a,b;
    for (int i = 0; i<m; i++) {
        cin >> aa[i] >> bb[i];
        a = aa[i]; b = bb[i];
        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;
        }
    }

    for (int i = 0; i<m; i++) {
        if (loc[aa[i]]!=loc[bb[i]]) {
            int la = loc[aa[i]];
            int lb = loc[bb[i]];
            for (int k = 0; k<n; k++) {if (loc[k]==lb) {loc[k]=a;}}
        }
    }
    //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";
    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 (x<occ) {
            c++;
        }
        occ = max(occ,y);
        /*else {
            occ = y;
        }*/
        i++;
    }

    cout << c;
}