Submission #926135

#	Time	Username	Problem	Language	Result	Execution time	Memory
926135		manizare	Sweeping (JOI20_sweeping)	C++14	100 / 100	7927 ms	1893256 KiB

sweeping

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#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 ;
const int maxn = 14e6 +  1e4 , maxp = 15e5 + 10 ;
int n,m,q,x[maxp] ,y[maxp] ,p[2][maxp] , cnt = 2 , c = 2 ;
vector <int> g[2][maxp] ;
 
int f(int v,int t){
    return (p[t][v]==0 ? v : p[t][v]=f(p[t][v],t)); 
}
void mrg(int v,int u , int t){
    u = f(u,t) ; v = f(v,t);
    if(v==u)return ;
    p[t][v]= u ;
    g[t][u].pb(v);
}
 
void reval(int v){
    x[v] = x[f(v,0)];
    y[v] = y[f(v,1)];
}
vector <int> rem ; 
void dfs(int v,int r,int t) {
    rem.pb(v); 
    for(int u :g[t][v]){
        if(f(u,t)!=r)continue ;
        dfs(u,r,t) ;
    }
}
 
struct rec{
    set <pii> s[2] ;
    int X , Y , d  , cl , cr ;
    int gl(){
        if(cl==0){
            cl = c ;c++;
        }
        return cl ;
    }
    int gr(){
        if(cr==0){
            cr = c ;c++;
        }
        return cr ;
    }
    void add(int v){
        p[0][v] = p[1][v] = 0 ;
        g[0][v].clear() ;g[1][v].clear(); 
        s[0].insert({y[v] , v}) ;
        s[1].insert({x[v] , v}) ;
    }
    void ers(int v){
        s[0].erase({y[v] , v}) ;
        s[1].erase({x[v] , v});
    }
    void up1(int l ,int t){
        rem.clear() ;
        while(sz(s[!t]) && (*s[!t].begin()).F <= l){
            int v = (*s[!t].begin()).S ; 
            dfs(v,v,t) ;
            s[!t].erase(s[!t].begin()) ;
        }
        for(int id : rem){
            reval(id) ;
        }
        for(int id : rem){
            ers(id) ;
        }
        for(int id : rem){
            if(t == 0){
                y[id] = n-l ;
            }else{
                x[id] = n-l ; 
            }
        }
    }
    void up2(int l,int t){
        int maxi = n-l ;
        vector <pii> az; 
        while(sz(s[t]) && (*s[t].begin()).F <= maxi){
            int id = (*s[t].begin()).S;  
            if(t==0){
                reval(id);
                az.pb({x[id] , id});
            }else{
                reval(id);
                az.pb({y[id] , id}) ;  
            }
            s[t].erase(s[t].begin()) ; 
        }
        if(sz(az)==0)return ;
        sort(all(az));
        if(t==0){
            y[az.back().S] = maxi ;
        }else{ 
            x[az.back().S] = maxi ;
        }
        s[t].insert({maxi,az.back().S}) ; 
        rep(i , 0, sz(az)-2){
            mrg(az[i].S , az[i+1].S , !t); 
        }
    }
};
rec r[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+1)/2 ;
    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]){
        ADD(id , r[p].gr() , m1 , Y  , d/2); 
    }else{
        ADD(id , r[p].gl() , X , m2 , d/2) ; 
    }
}
void upd(int l , int t , int p = 1,int X= 0 , int Y= 0, int d= n){
    r[p].X = X ; r[p].Y = Y ; r[p].d = (d+1)/2 ;
    if(d==0)return ; 
    if((t==0 && X > l) || (t==1 && Y > l))return ;
    int m1 = X+(d+1)/2 ,  m2 = Y+(d+1)/2 ;
    if((t==0&& l+(d&1)<=m1) || (t==1&& l+(d&1)<=m2)){
        r[p].up1(l,t); 
        while(sz(rem)){
            int v = rem.back() ;
            ADD(v); 
            rem.pop_back() ;
        }
        if(t==0)upd(l , t ,r[p].gl() , X , m2 , d/2);
        else upd(l,t, r[p].gr() , m1 , Y , d/2) ;
    }
    if((t==0&&l >= m1) || (t==1&&l >= m2)){
        r[p].up2(l,t);
        if(t==0)upd(l, t , r[p].gr() , m1 , Y  , d/2); 
        else upd(l,t , r[p].gl() , X  , m2 , d/2) ;
    }
}
 
 
signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q ;
    int id = 1; 
    rep(i , 1 , m){
        cin >> x[id] >> y[id] ;
        ADD(id) ;
        id++;
    }
    while(q--){
        int t ;
        cin >> t ;
        if(t==1){
            int a ;cin >> a;
            reval(a);
            cout << x[a] << " " << y[a] << "\n" ; 
        }
        if(t==3){
            int l ;
            cin >> l ;
            upd(l , 0);   
        }
        if(t==2){
            int l ;
            cin >> l ;
            upd(l , 1);
        }
        if(t==4){
            cin >> x[id] >> y[id];
            ADD(id) ;
            id++;
        }
    }
    return 0;
}
 
/*
 
*/

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