oj.uz

답안 #579250

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
579250 2022-06-18T15:57:04 Z radal 청소 (JOI20_sweeping) C++17
74 / 100
 8462 ms 441128 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 = 2e6+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[u] > X[v]) || (!f && Y[u] > Y[v])) 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;
        if (X[i]+Y[i] == n) continue;
        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
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 298060 KB Output is correct
2 Incorrect 158 ms 297884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4253 ms 383140 KB Output is correct
2 Correct 3889 ms 382048 KB Output is correct
3 Correct 3994 ms 382320 KB Output is correct
4 Correct 3116 ms 370188 KB Output is correct
5 Correct 8462 ms 396252 KB Output is correct
6 Correct 6834 ms 386224 KB Output is correct
7 Correct 3866 ms 380736 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3962 ms 388832 KB Output is correct
2 Correct 4789 ms 404152 KB Output is correct
3 Correct 1412 ms 383260 KB Output is correct
4 Correct 5610 ms 441128 KB Output is correct
5 Correct 4553 ms 411644 KB Output is correct
6 Correct 2841 ms 406660 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3962 ms 388832 KB Output is correct
2 Correct 4789 ms 404152 KB Output is correct
3 Correct 1412 ms 383260 KB Output is correct
4 Correct 5610 ms 441128 KB Output is correct
5 Correct 4553 ms 411644 KB Output is correct
6 Correct 2841 ms 406660 KB Output is correct
7 Correct 4000 ms 393896 KB Output is correct
8 Correct 3962 ms 395184 KB Output is correct
9 Correct 3973 ms 393068 KB Output is correct
10 Correct 2877 ms 383236 KB Output is correct
11 Correct 6611 ms 415648 KB Output is correct
12 Correct 7274 ms 410600 KB Output is correct
13 Correct 6991 ms 432300 KB Output is correct
14 Correct 303 ms 301620 KB Output is correct
15 Correct 1839 ms 380256 KB Output is correct
16 Correct 3612 ms 388672 KB Output is correct
17 Correct 3753 ms 395448 KB Output is correct

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 298060 KB Output is correct
2 Incorrect 158 ms 297884 KB Output isn't correct
3 Halted 0 ms 0 KB -