Submission

Score: 100

User: Nathlol2

Problemset: Tech Sprites

Language: cpp

Time: 1.763 second

Submitted On: 2025-05-28 09:25:24

/*
* Author : NathInwza007
* Created : 2025-05-24 19:37:22 UTC+7
*/

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

#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define sc second
#define inf (int)2e9
#define INF (ll)1e18
#define MOD (ll)1000000007
//998244353

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define vt vector
#define pb push_back
#define eb emplace_back
#define all(arrname) (arrname).begin(), (arrname).end()
#define rall(arrname) (arrname).rbegin(), (arrname).rend()
#define sz(arrname) (int)(arrname).size()
const int mxN = 1e6 + 5;
vt<vt<int>> adj(mxN);
vt<pll> a(mxN);
vt<bool> vis(mxN, false);
void dfs(int x, pll &mx, pll &mn){
    vis[x] = 1;
    for(auto v : adj[x]){
        if(!vis[v]){
            mx = max(mx, a[v]);
            mn = min(mn, a[v]);
            dfs(v, mx, mn);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        cin >> a[i].fi >> a[i].sc;
    }
    for(int i = 0;i<m;i++){
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    vt<pair<pll, pll>> p;
    for(int i = 0;i<n;i++){
        if(!vis[i]){
            pll mn = {a[i].fi, a[i].sc};
            pll mx = {a[i].fi, a[i].sc};
            dfs(i, mx, mn);
            p.eb(mn, mx);
        }
    }
    sort(all(p));
    int ans = 0;
    pll now = p[0].sc;
    for(int i = 1;i<sz(p);i++){
        while(i < sz(p) && p[i].fi < now){
            now = max(now, p[i].sc);
            ++i;
            ++ans;
        }
        now = p[i].sc;
    }
    cout << ans;
    return 0;
}