oj.uz

Submission #579265

# Submission time Handle Problem Language Result Execution time Memory
579265 2022-06-18T16:50:24 Z radal Sweeping (JOI20_sweeping) C++17
100 / 100
 9336 ms 1078104 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 893180 KB Output is correct
2 Correct 418 ms 892860 KB Output is correct
3 Correct 432 ms 893184 KB Output is correct
4 Correct 400 ms 893052 KB Output is correct
5 Correct 405 ms 893072 KB Output is correct
6 Correct 399 ms 892900 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3727 ms 978104 KB Output is correct
2 Correct 3424 ms 977076 KB Output is correct
3 Correct 3417 ms 977304 KB Output is correct
4 Correct 2825 ms 965324 KB Output is correct
5 Correct 7522 ms 991340 KB Output is correct
6 Correct 6133 ms 981280 KB Output is correct
7 Correct 3406 ms 975628 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3484 ms 983668 KB Output is correct
2 Correct 3850 ms 979408 KB Output is correct
3 Correct 1425 ms 959356 KB Output is correct
4 Correct 4907 ms 1016824 KB Output is correct
5 Correct 4115 ms 987960 KB Output is correct
6 Correct 2842 ms 982436 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3484 ms 983668 KB Output is correct
2 Correct 3850 ms 979408 KB Output is correct
3 Correct 1425 ms 959356 KB Output is correct
4 Correct 4907 ms 1016824 KB Output is correct
5 Correct 4115 ms 987960 KB Output is correct
6 Correct 2842 ms 982436 KB Output is correct
7 Correct 3772 ms 969812 KB Output is correct
8 Correct 3628 ms 971008 KB Output is correct
9 Correct 3631 ms 968672 KB Output is correct
10 Correct 2691 ms 959360 KB Output is correct
11 Correct 5957 ms 991564 KB Output is correct
12 Correct 6800 ms 986616 KB Output is correct
13 Correct 6332 ms 1008432 KB Output is correct
14 Correct 504 ms 893100 KB Output is correct
15 Correct 1752 ms 961656 KB Output is correct
16 Correct 3241 ms 964656 KB Output is correct
17 Correct 3378 ms 971624 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 893180 KB Output is correct
2 Correct 418 ms 892860 KB Output is correct
3 Correct 432 ms 893184 KB Output is correct
4 Correct 400 ms 893052 KB Output is correct
5 Correct 405 ms 893072 KB Output is correct
6 Correct 399 ms 892900 KB Output is correct
7 Correct 3727 ms 978104 KB Output is correct
8 Correct 3424 ms 977076 KB Output is correct
9 Correct 3417 ms 977304 KB Output is correct
10 Correct 2825 ms 965324 KB Output is correct
11 Correct 7522 ms 991340 KB Output is correct
12 Correct 6133 ms 981280 KB Output is correct
13 Correct 3406 ms 975628 KB Output is correct
14 Correct 3484 ms 983668 KB Output is correct
15 Correct 3850 ms 979408 KB Output is correct
16 Correct 1425 ms 959356 KB Output is correct
17 Correct 4907 ms 1016824 KB Output is correct
18 Correct 4115 ms 987960 KB Output is correct
19 Correct 2842 ms 982436 KB Output is correct
20 Correct 3772 ms 969812 KB Output is correct
21 Correct 3628 ms 971008 KB Output is correct
22 Correct 3631 ms 968672 KB Output is correct
23 Correct 2691 ms 959360 KB Output is correct
24 Correct 5957 ms 991564 KB Output is correct
25 Correct 6800 ms 986616 KB Output is correct
26 Correct 6332 ms 1008432 KB Output is correct
27 Correct 504 ms 893100 KB Output is correct
28 Correct 1752 ms 961656 KB Output is correct
29 Correct 3241 ms 964656 KB Output is correct
30 Correct 3378 ms 971624 KB Output is correct
31 Correct 3381 ms 982644 KB Output is correct
32 Correct 3962 ms 989216 KB Output is correct
33 Correct 1705 ms 991592 KB Output is correct
34 Correct 4552 ms 1020304 KB Output is correct
35 Correct 4500 ms 1020320 KB Output is correct
36 Correct 3195 ms 983644 KB Output is correct
37 Correct 9336 ms 1078104 KB Output is correct
38 Correct 7521 ms 1023156 KB Output is correct
39 Correct 6366 ms 1019536 KB Output is correct
40 Correct 3606 ms 997792 KB Output is correct