Submission #925727

#	Time	Username	Problem	Language	Result	Execution time	Memory
925727		manizare	Sweeping (JOI20_sweeping)	C++14	0 / 100	2021 ms	1928616 KiB

sweeping

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ; 
using namespace std ;   
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 5e5 +  10 , maxp = 4000, lg = 22 , mod = 998244353 ,  sq =700 , inf = 1e9 ;
int n,m,q,x[maxn] ,y[maxn] ,px[maxn] , py[maxn] , cnt = 2 ;
vector <int> gx[maxn],gy[maxn] ;

int fx(int v){
    return (px[v]==0 ? v : px[v]=fx(px[v])); 
}
int fy(int v){
    return (py[v]==0 ? v : py[v]=fy(py[v])); 
}
void mx(int v,int u){
    u = fx(u) ; v = fx(v);
    if(v==u)return ;
    px[v]= u ;
    gx[u].pb(v);
}
void my(int v,int u){
    u = fy(u) ; v = fy(v);
    if(v==u)return ;
    py[v]= u ;
    gy[u].pb(v);
}
void reval(int v){
    x[v] = x[fx(v)];
    y[v] = y[fy(v)];
}
vector <int> rem ; 
void dfsy(int v,int r){
    rem.pb(v); 
    for(int u :gy[v]){
        if(fy(u)!=r)continue ;
        dfsy(u,r) ;
    }
}

struct rec{
    set <pii> sx , sy ;
    int X , Y , d , cl , cr ; 
    void add(int v){
        px[v] = py[v] = 0 ;
        gx[v].clear() ;gy[v].clear(); 
        sx.insert({y[v] , v}) ;
        sy.insert({x[v] , v}) ;
    }
    void ers(int v){
        if(fx(v) == v){
            sx.erase({y[v] , v}) ;
        }
        if(fy(v) == v){
            sy.erase({x[v] , v});
        }
    }
    void upx(int l){
        if(l < X)return ; 
        if(l <= X+d){
            rem.clear() ;
            while(sz(sy) && (*sy.begin()).F <= l){
                int v = (*sy.begin()).S ; 
                dfsy(v,v) ;
                sy.erase(sy.begin()) ;
            }
            for(int id : rem){
                reval(id) ;
                ers(id);
            }
        }else{
            int maxi = n-l ;
            vector <pii> az; 
            while(sz(sx) && (*sx.begin()).F <= maxi){
                int id = (*sx.begin()).S;  
                az.pb({x[id] , id}); 
                sx.erase(sx.begin()) ; 
            }
            if(sz(az)==0)return ;
            sort(all(az));
            y[az.back().S] = maxi ;
            sx.insert({maxi,az.back().S}) ;
            rep(i , 0, sz(az)-2){
                mx(az[i].S , az[i+1].S); 
            }
        }
    }
};
rec r[10*maxn] ;

void ADD(int id , int p = 1  , int X = 0 , int Y = 0 , int d = n){
    r[p].X = X ; r[p].Y = Y ; r[p].d = d ;
    int m1 = X+(d+1)/2 ,  m2 = Y+(d+1)/2 ;
    if(d==0){
        r[p].add(id) ;
        return ; 
    }
    if(m1 > x[id] && m2 > y[id]){
        r[p].add(id) ;
        return ;
    }
    if(m1 <= x[id]){
        if(r[p].cr == 0){
            r[p].cr = cnt ; cnt++;
        }
        ADD(id , r[p].cr , m1 , Y  , d/2); 
    }else{
        if(r[p].cl == 0){
            r[p].cl = cnt ; cnt ++ ;
        }
        ADD(id , r[p].cl, X , m2 , d/2) ; 
    }
}
void updx(int l , int p = 1,int X= 0 , int Y= 0, int d= n){
    r[p].X = X ; r[p].Y = Y ; r[p].d = d ;
    if(d==0)return ; 
    if(X > l)return ;
    int m1 = X+(d+1)/2 ,  m2 = Y+(d+1)/2 ;
    r[p].upx(l);
    if(l <= X+d){
        if(r[p].cl == 0){
            r[p].cl = cnt ; cnt++;
        }
        while(sz(rem)){
            int v = rem.back() ;
            r[r[p].cl].add(v);
            rem.pop_back() ;
        }
        updx(l ,r[p].cl, X , m2 , d/2);
        return ;
    }
    updx(l , r[p].cr , m1 , Y  , d/2); 
}


signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q ; 
    int id = 1;
    r[1].X = 0 ; r[1].Y = 0 ; r[1].d = n ; 
    rep(i , 1 ,m){
        cin >> x[id]>> y[id];
        ADD(id); 
        id++;
    }
    rep(i ,1 , q){
        int t ;
        cin >> t ;
        if(t==1){
            int k ;
            cin >> k ;
            reval(k);
            cout << x[k] << " "<< y[k] << "\n";
        }
        if(t==4){
            cin >> x[id] >> y[id] ;
            ADD(id);
            id++;
        }
        if(t==2){
            int l ;
            cin >> l ;
            updx(l) ;
        }
    }
    return 0;
}

/*

*/

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