Submission #579265

#	Time	Username	Problem	Language	Result	Execution time	Memory
579265		radal	Sweeping (JOI20_sweeping)	C++17	100 / 100	9336 ms	1078104 KiB

sweeping

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse4,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 6e6+20,mod = 1e9+7,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k,int p){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%p;
        a = 1ll*a*a%p;
        k >>= 1;
    } 
    return z; 
}
int par[N][2]; // x y
int cnt,lc[N],rc[N],cnt_po,cur[N];
int X[N],Y[N],n,m,q;
vector<int> adj[N][2];
set<pll> st[N][2];

int getpar(int v,bool f){
    if (par[v][f] == v) return v;
    return par[v][f] = getpar(par[v][f],f);
}

void mg(int u,int v,bool f){
    u = getpar(u,f);
    v = getpar(v,f);
    if (u == v) return;
    if ((f && X[getpar(u,0)] > X[getpar(v,0)]) || (!f && Y[getpar(u,1)] > Y[getpar(v,1)])) swap(u,v);
    par[u][f] = v;
    adj[v][f].pb(u);
}

void add_po(int i,int x,int y,int v){
    if (X[i]+Y[i] == n){
        par[i][0] = i;
        par[i][1] = i;
        adj[i][0].clear();
        adj[i][1].clear();
        cur[i] = -1;
        return;
    }
    int h = n-x-y;
    if (X[i] - x > h/2){
        if (lc[v] == -1){
            cnt++;
            lc[v] = cnt;
        }
        add_po(i,h/2+x,y,lc[v]);
        return;
    }
    if (Y[i] - y > (h+1)/2){
        if (rc[v] == -1){
            cnt++;
            rc[v] = cnt;
        }
        add_po(i,x,y+(h+1)/2,rc[v]);
        return;
    }
    par[i][0] = par[i][1] = i;
    adj[i][0].clear();
    adj[i][1].clear();
    st[v][0].insert({X[i],i});
    st[v][1].insert({Y[i],i});
    cur[i] = v;
}

void dfs(int v,int i,vector<int>& ve,bool f){
    if (cur[v] != i) return;
    ve.pb(v);
    for (int u : adj[v][f]) dfs(u,i,ve,f);
}

void vert(int l,int x,int y,int v){
    if (l < x) return;
    int h = n-x-y;
    int top = n-l;
    if (l >= x+(h/2)){
        vector<pll> ve;
        for (pll p : st[v][1]){
            if (p.X > top) break;
            ve.pb(p);
        }
        int sz = ve.size();
        if (!sz){
            if (lc[v] != -1) vert(l,x+h/2,y,lc[v]);
            return;
        }
        for(pll p : ve) st[v][1].erase(p);
        rep(i,0,sz-1) mg(ve[i].Y,ve[i+1].Y,1);
        int u = getpar(ve[0].Y,1);
        Y[u] = top;
        st[v][1].insert({top,u});
        if (lc[v] != -1) vert(l,x+h/2,y,lc[v]);
        return;
    }
    vector<int> ve;
    for (pll p : st[v][0]){
        if (p.X > l) break;
        dfs(p.Y,v,ve,0);
    }
    for (int u : ve){
        st[v][0].erase({X[u],u});
        st[v][1].erase({Y[u],u});
        Y[u] = top;
        X[u] = X[getpar(u,0)];
    }
    if (!ve.empty() && rc[v] == -1){
        cnt++;
        rc[v] = cnt;
    }
    for (int u : ve){
        add_po(u,x,y+(h+1)/2,rc[v]);
    }
    if (rc[v] != -1) vert(l,x,y+(h+1)/2,rc[v]);
}

void horz(int l,int x,int y,int v){
    if (l < y) return;
    int h = n-x-y;
    int top = n-l;
    if (l >= y+((h+1)/2)){
        vector<pll> ve;
        for (pll p : st[v][0]){
            if (p.X > top) break;
            ve.pb(p);
        }
        int sz = ve.size();
        if (!sz){
            if (rc[v] != -1) horz(l,x,y+(h+1)/2,rc[v]);
            return;
        }
        for(pll p : ve) st[v][0].erase(p);
        rep(i,0,sz-1) mg(ve[i].Y,ve[i+1].Y,0);
        int u = getpar(ve[0].Y,0);
        X[u] = top;
        st[v][0].insert({top,u});
        if (rc[v] != -1) horz(l,x,y+(h+1)/2,rc[v]);
        return;
    }
    vector<int> ve;
    for (pll p : st[v][1]){
        if (p.X > l) break;
        dfs(p.Y,v,ve,1);
    }
    for (int u : ve){
        st[v][0].erase({X[u],u});
        st[v][1].erase({Y[u],u});
        Y[u] = Y[getpar(u,1)];
        X[u] = top;
    }
    if (!ve.empty() && lc[v] == -1){
        cnt++;
        lc[v] = cnt;
    }
    for (int u : ve){
        add_po(u,x+h/2,y,lc[v]);
    }
    if (lc[v] != -1) horz(l,x+h/2,y,lc[v]);
}

int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    memset(lc,-1,sizeof lc);
    memset(rc,-1,sizeof rc);
    cin >> n >> m >> q;
    rep(i,1,m+1){
        cin >> X[i] >> Y[i];
        par[i][0] = i;
        par[i][1] = i;
        add_po(i,0,0,0);
    }
    cnt_po = m;
    rep(j,0,q){
        int ty;
        cin >> ty;
        if (ty == 1){
            int v;
            cin >> v;
            cout << X[getpar(v,0)] << ' ' << Y[getpar(v,1)] << endl;
            continue;
        }
        if (ty == 4){
            cnt_po++;
            cin >> X[cnt_po] >> Y[cnt_po];
            rep(i,0,2) par[cnt_po][i] = cnt_po;
            add_po(cnt_po,0,0,0);
            continue;
        }
        int l;
        cin >> l;
        if (ty == 2)
            horz(l,0,0,0);
        else if (ty == 3)
            vert(l,0,0,0);
    }
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25