Submission

Score: 100

User: Winzzwz

Problemset: Tech Sprites

Language: cpp

Time: 1.306 second

Submitted On: 2025-05-24 19:25:50

/*
STATEMENT: https://api.otog.in.th/problem/doc/1086
FILE: toi21_tech_sprites.cpp
AUTHOR: Win [Discord: @un.de.fined, Github: https://github.com/Winzzwz]
TIME: 5/24/2025, 4:22:10 PM
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;

struct hee {
    int a,b,idx;
    bool operator < (const hee&o) const {
        if (a != o.a) return a < o.a;
        return b < o.b;
    }
};

int n,m,a,b,ans,p[1000010],sz[1000010],mx[1000010],mn[1000010],r[1000010],gmn[1000010];
hee t[1000010], temp[1000010];
set<pii> st;

int fr(int i) {
    if (i == p[i]) return i;
    return p[i] = fr(p[i]);
}

int uni(int u, int v) {
    u = fr(u); v = fr(v);
    if (u == v) return 0;
    p[u] = v;
    sz[v] += sz[u];
    sz[u] = 0;
    mx[v] = max(mx[v],mx[u]);
    mn[v] = min(mn[v],mn[u]);
    return 1;
}

int main() {
    // cin.tie(0)->sync_with_stdio(0);
    scanf("%d %d",&n,&m);
    for (int i = 1; i <= n; i++) {
        p[i] = mx[i] = mn[i] = i;
        sz[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d %d",&a,&b);
        t[i] = {a,b,i};
        temp[i] = {a,b,i};
    }
    sort(t+1,t+1+n);
    for (int i = 1; i <= n; i++) {
        r[t[i].idx] = i;
    }
    while (m--) {
        scanf("%d %d",&a,&b);
        int aidx = r[a], bidx = r[b];
        uni(aidx,bidx);
    }
    for (int i = 1; i <= n; i++) {
        st.insert({mn[fr(i)],fr(i)});
        gmn[fr(i)] = mn[fr(i)];
    }
    int kuy = 1;
    for (auto xx : st) {
        int x = xx.second;
        if (mx[x]-mn[x]+1 == sz[x] || mx[x] < kuy) continue;
        for (int i = gmn[x]; i <= mx[x]; i++) {
            if (uni(i,x)) ans++;
            gmn[x] = i;
            kuy = i;
            if (mx[x]-mn[x]+1 == sz[x]) break;
        }
    }
    printf("%d",ans);
    return 0;
}