Submission #1040339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040339		hotboy2703	Sweeping (JOI20_sweeping)	C++17	100 / 100	2436 ms	387452 KiB

sweeping

    #include<bits/stdc++.h>
    using ll = int;
    using namespace std;
    #define pll pair <ll,ll>
    #define fi first
    #define se second
    #define MP make_pair
    #define sz(a) (ll((a).size()))
    #define BIT(mask,i) (((mask) >> (i))&1)
    #define MASK(i) (1LL << (i))
    const ll INF = 1e9;
    const ll MAXN = 1.5e6+100;
    struct query{
        ll t,p,x,y;
    };
    pll ans[MAXN];
    ll val[MAXN*2];
    ll dsu[MAXN*2];
    ll side[MAXN*2];
    vector <ll> comp[MAXN*2];

    ll n,m,q;
    ll join(ll x,ll y){
        if (sz(comp[x]) < sz(comp[y]))swap(x,y);
        for (auto z:comp[y]){comp[x].push_back(z);dsu[z] = x;}
        return x;
    }
    void dnc(ll l,ll r,vector <query> &all){
        ll mid = (l + r) >> 1;
        vector <query> L,R;
        if (sz(all)==0)return;
        for (auto x:all){
            if (x.t == 4){
                dsu[x.p<<1] = x.p<<1;
                dsu[x.p<<1|1] = x.p<<1|1;
                comp[x.p<<1] = {x.p<<1};
                comp[x.p<<1|1] = {x.p<<1|1};
                val[x.p<<1] = x.x;
                val[x.p<<1|1] = x.y;
                side[x.p] = 0;
            }
        }
        if (l==r){
            for (auto [t,p,x,y]:all){
                if (t==1){
                    ans[x] = MP(val[p<<1],val[p<<1|1]);  
                }
            }
            return;
        }
        priority_queue <pll,vector <pll>, greater <> > px,py;
        for (auto cur:all){
            auto [t,p,x,y] = cur;
            if (t==1){
                if (side[p] == 0){
                    // cout<<l<<' '<<r<<' '<<x<<' '<<p<<endl;
                    ans[x] = MP(val[dsu[p<<1]],val[dsu[p<<1|1]]); 
                }
                else if (side[p] == 1)L.push_back(cur);
                else if (side[p] == 2){R.push_back(cur);}
            }
            if (t==2){
                if (n-x>=mid+1){
                    R.push_back(cur);
                    while (!py.empty() && py.top().fi <= x){
                        ll u = py.top().se;
                        py.pop();
                        for (auto z:comp[u]){
                            if (side[z>>1]==0){
                                // cout<<l<<' '<<r<<' '<<(z>>1)<<' '<<val[dsu[16]]<<' '<<val[dsu[17]]<<endl;
                                side[z>>1] = 2;
                                z = z>>1;
                                // if (z==8)cout<<"SUS "<<l<<' '<<r<<' '<<side[z]<<' '<<val[z<<1]<<' '<<val[z<<1|1]<<'\n';
                                R.push_back({4,z,n-x,val[u]});
                            }
                        }
                    }
                    
                }
                else{
                    ll r = 0;
                    while (!px.empty() && px.top().fi <= n-x){
                        ll u = px.top().se;
                        px.pop();
                        // cout<<l<<' '<<r<<' '<<u<<endl;
                        r = r?join(r,u):u;
                    }
                    if (r){
                        val[r] = n-x;
                        // cout<<val[dsu[16]]<<endl;
                        px.push(MP(val[r],r));
                    }
                    L.push_back(cur);
                }
            }
            if (t==3){
                if (x <= mid){
                    L.push_back(cur);
                    while (!px.empty() && px.top().fi <= x){
                        ll u = px.top().se;
                        px.pop();
                        for (auto z:comp[u]){
                            if (side[z>>1]==0){
                                side[z>>1] = 1;
                                // val[z] = val[u];
                                // val[z^1] = n-x;
                                z=z>>1;
                                L.push_back({4,z,val[u],n-x});
                            }
                        }
                    }
                    
                }
                else{
                    
                    ll r = 0;
                    while (!py.empty() && py.top().fi <= n-x){
                        ll u = py.top().se;
                        py.pop();
                        r = r?join(r,u):u;
                    }
                    if (r){
                        val[r] = n-x;
                        py.push(MP(val[r],r));
                    }
                    R.push_back(cur);
                }
            }
            if (t==4){
                if (x >= mid + 1){
                    R.push_back(cur);
                    side[p] = 2;
                }
                else if (y >= n-mid){
                    L.push_back(cur);
                    side[p] = 1;
                }
                else{
                    px.push(MP(val[p<<1],p<<1));
                    py.push(MP(val[p<<1|1],p<<1|1));
                }
            }
        }
        
        dnc(l,mid,L);
        dnc(mid+1,r,R);
    }
    int main(){
        ios_base::sync_with_stdio(0);cin.tie(nullptr);
        // freopen("1.inp","r",stdin);
        // freopen("1.out","w",stdout);
        cin>>n>>m>>q;
        vector <query> all;
        ll ptr = 0;
        for (ll i = 1;i <= m;i ++){
            ll x,y;
            cin>>x>>y;
            all.push_back({4,++ptr,x,y});
        }
        ll cnt=0;
        for (ll i = 1;i <= q;i ++){
            ll t;
            cin>>t;
            if (t==1){
                ll p;
                cin>>p;
                all.push_back({1,p,++cnt,-1});
            }
            if (t==2){
                ll x;
                cin>>x;
                all.push_back({2,-1,x,-1});
            }
            if (t==3){
                ll x;
                cin>>x;
                all.push_back({3,-1,x,-1});
            }
            if (t==4){
                ll x,y;
                cin>>x>>y;
                all.push_back({4,++ptr,x,y});
            }
        }
        dnc(0,n,all);
        for (ll i = 1;i <= cnt;i ++)cout<<ans[i].fi<<' '<<ans[i].se<<'\n';
        return 0;
    }

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