Submission #1040105

#TimeUsernameProblemLanguageResultExecution timeMemory
1040105hotboy2703Sweeping (JOI20_sweeping)C++17
100 / 100
3394 ms931560 KiB
#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; 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){ 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); // 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...