Submission #1040098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040098		hotboy2703	Sweeping (JOI20_sweeping)	C++17	100 / 100	15966 ms	952224 KiB

sweeping

#include<bits/stdc++.h>
using ll = long long;
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 = 1e18;
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;

    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){
                
                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]});
                        }
                    }
                }R.push_back(cur);
                
            }
            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){
                
                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});
                        }
                    }
                }
                L.push_back(cur);
            }
            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);
    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