Submission #216143

#TimeUsernameProblemLanguageResultExecution timeMemory
216143ryanseeSweeping (JOI20_sweeping)C++14
0 / 100
940 ms551192 KiB
#include "bits/stdc++.h" using namespace std; #define FAST ios_base::sync_with_stdio(false); cin.tie(0); #define pb push_back #define eb emplace_back #define ins insert #define ph push #define f first #define s second #define cbr cerr << "hi\n" #define mmst(x, v) memset((x), v, sizeof ((x))) #define siz(x) ll(x.size()) #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng) inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); } typedef long long ll; typedef long double ld; #define FOR(i,s,e) for(ll i=s;i<=ll(e);++i) #define DEC(i,s,e) for(ll i=s;i>=ll(e);--i) typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi; #define LLINF ((long long)1e18) #define INF int(1e9+1e6) #define MAXN (1500006) // change MAXN later struct Query{ ll t, ind, l, x, y, QI; };vector<Query> Q; ll n,m,q,cnt; pi pos[MAXN],ans[MAXN]; vector<ll> v[MAXN]; struct ufds_ { int p[MAXN]; void init(ll x) { FOR(i,0,x+1) p[i]=i, v[i].clear(), v[i].pb(i); } void merge(int x,int y){ x=find(x),y=find(y); if(x==y)return; if(siz(v[x])>siz(v[y]))swap(x,y); p[x]=y; for(auto i:v[x]) v[y].pb(i); v[x].clear(); } int find(int x) { return (p[x]==x)?x:p[x]=find(p[x]); } bool same(int x,int y) { return find(x)==find(y); } } ufds; void dnc(ll x,ll y,vector<Query> Q){ if(Q.empty())return; sort(all(Q),[](Query x,Query y){return x.QI<y.QI;}); ll diff=n-x-y; if(diff == 0) { // do something(?) just answer the Queries(?) for(auto i:Q) if(i.t==1) ans[i.ind]={x,y}; return; } ll X=x+(diff+1)/2, Y=y+diff/2+1, cnt=0, act=0; ufds.init(Q.size()*2+3); vector<bool> gone(Q.size(), 0); vector<Query> UP, RI; priority_queue<pi,vector<pi>,greater<pi>> px, py; map<ll,ll> gcnt, cntQ; vector<ll> xnow(Q.size(),0), ynow(Q.size(),0); for(auto i:Q) if(i.t==4) { xnow[cnt]=i.x, ynow[cnt]=i.y; gcnt[i.ind]=cnt; cntQ[cnt]=act; ++ cnt, ++ act; } else ++ act; cnt=0; for(auto i:Q){ if(i.t==1){// reconsider index pls Query tmp = i; i.l=gcnt[i.l]; if(gone[i.l]){ // decide whether to push Query into UP or RI if(xnow[ufds.find(i.l<<1|1)>>1] >= X) { assert(ynow[ufds.find(i.l<<1)>>1] < Y); RI.pb(tmp); }else if(ynow[ufds.find(i.l<<1)>>1] >= Y) { UP.pb(tmp); }else { // cerr<<x<<' '<<y<<'\n'; assert(0); } }else{ ans[i.ind]=pi(xnow[ufds.find(i.l<<1)>>1],ynow[ufds.find(i.l<<1|1)>>1]); } }else if(i.t==2){ // horizontal if(n-i.l >= X) { // protrudes RI.pb(i); // all y <= i.l, set gone = 1, push RI, rmbr to set xnow, cos queries need to go where to go while(py.size()) { if(py.top().f > i.l) break; ll x=py.top().s; py.pop(); if(gone[x>>1])continue; assert(ufds.find(x)==x); xnow[x>>1]=n-i.l;assert(n-i.l>=X); for(auto i:v[x]) assert(ufds.find(i)==x), gone[i>>1]=1, RI.pb(Q[cntQ[i>>1]]); } }else {// def taller than square UP.pb(i); ll lst=-1; while(px.size()){ if(px.top().f>n-i.l) break; ll x=px.top().s; px.pop(); if(gone[x>>1])continue; if(~lst){ ufds.merge(lst,x); } lst=x; } if(~lst) lst=ufds.find(lst), xnow[lst>>1]=n-i.l, px.emplace(xnow[lst>>1],lst); } }else if(i.t==3){ // vertical if(n-i.l>=Y){//protrudes UP.pb(i); while(px.size()){ if(px.top().f>i.l)break; ll x=px.top().s; px.pop(); if(gone[x>>1])continue; assert(ufds.find(x)==x); ynow[x>>1]=n-i.l;assert(n-i.l>=Y); for(auto i:v[x]) assert(ufds.find(i)==x), gone[i>>1]=1, UP.pb(Q[cntQ[i>>1]]); } }else{//def wider than sqaure RI.pb(i); ll lst=-1; while(py.size()){ if(py.top().f>n-i.l)break; ll x=py.top().s; py.pop(); if(gone[x>>1])continue; if(~lst) { ufds.merge(lst, x); } lst=x; } if(~lst) lst=ufds.find(lst), ynow[lst>>1]=n-i.l, py.emplace(ynow[lst>>1],lst); } }else{ // add new point if(i.x >= X) { assert(i.y < Y); gone[cnt]=1, RI.pb(i); }else if(i.y >= Y) { assert(i.x < X); gone[cnt]=1, UP.pb(i); }else{ px.emplace(i.x, cnt<<1); py.emplace(i.y, cnt<<1|1); } ++ cnt; } } // cannot change the array pos at the end, as in separate dncs, some moves might end up coming first // cerr<<X<<' '<<y<<" RI: "; // for(auto i:RI) cerr<<i.QI<<' '; // cerr<<'\n'; // cerr<<x<<' '<<Y<<" UP: "; // for(auto i:UP) cerr<<i.QI<<' '; // cerr<<'\n'; dnc(X,y,RI); dnc(x,Y,UP); } int main(){ FAST cin>>n>>m>>q; FOR(i,1,m){ ++ cnt; cin>>pos[cnt].f>>pos[cnt].s; Q.pb({4,cnt,-1,pos[cnt].f,pos[cnt].s}); } FOR(ii,1,q){ ll t;cin>>t; if(t<=3){ ll l;cin>>l; Q.pb({t,ii,l,-1,-1}); }else{ ++ cnt; cin>>pos[cnt].f>>pos[cnt].s; Q.pb({4,cnt,-1,pos[cnt].f,pos[cnt].s}); } } FOR(i,0,siz(Q)-1)Q[i].QI=i; mmst(ans,-1); dnc(0,0,Q); FOR(i,1,q)if(ans[i]!=pi(-1,-1))cout<<ans[i].f<<' '<<ans[i].s<<'\n'; } /* 20 1 7 1 0 2 18 3 9 3 10 3 3 2 9 3 12 1 1 */
#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...