Submission #261249

#TimeUsernameProblemLanguageResultExecution timeMemory
261249mhy908Sweeping (JOI20_sweeping)C++14
0 / 100
8010 ms751112 KiB
#include <bits/stdc++.h> #define eb emplace_back #define mp make_pair #define F first #define S second #define all(x) x.begin(), x.end() using namespace std; typedef long long LL; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; pair<pii, int> rng[1500010]; int n, m, q, re; struct SWP_SEG{ struct NODE{ NODE *lc, *rc; NODE(){lc=rc=0;} map<int, vector<int> > l, r; vector<int> lnum, rnum, rv, ch; struct INC_DSU{ vector<int> par; void ins(){int sz=par.size(); par.eb(sz);} int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);} void mergepar(int a, int b){par[findpar(a)]=findpar(b);} }ufl, ufr; pii get_range(int num){ int ul=ufl.findpar(num); int ur=ufr.findpar(num); return mp(lnum[ul], rnum[ur]); } void ins(int s, int e, pii rn, int num){ rng[num]=mp(mp(s, e), lnum.size()); rv.eb(num); ufl.ins(); ufr.ins(); lnum.eb(rn.F); rnum.eb(rn.S); ch.eb(0); if(l[rn.F].size())ufl.mergepar(rng[num].S, l[rn.F].back()); if(r[rn.S].size())ufr.mergepar(rng[num].S, r[rn.S].back()); l[rn.F].eb(rng[num].S); r[rn.S].eb(rng[num].S); } }*rt; SWP_SEG(){rt=new NODE();} pii query(NODE *nd, int s, int e, int num){ if(s==rng[num].F.F&&e==rng[num].F.S)return nd->get_range(rng[num].S); if(rng[num].F.S<=(s+e)/2)return query(nd->lc, s, (s+e)/2, num); return query(nd->rc, (s+e)/2+1, e, num); } void overkill_lft(NODE *nd, int s, int e, int num){ vector<pair<pii, int> > vc; auto it=nd->r.end(); while(it!=nd->r.begin()){ it--; if(it->F<num){ it++; break; } for(auto i:it->S){ if(nd->ch[i])continue; nd->ch[i]=1; vc.eb(mp(num, it->F), i); } } nd->r.erase(it, nd->r.end()); if(vc.size()==0)return; if(!nd->rc)nd->rc=new NODE(); for(auto i:vc)upd_ins(nd->rc, (s+e)/2+1, e, i.F, nd->rv[i.S]); } void overkill_rgt(NODE *nd, int s, int e, int num){ vector<pair<pii, int> > vc; auto it=nd->l.begin(); while(it!=nd->l.end()){ if(it->F>num)break; for(auto i:it->S){ if(nd->ch[i])continue; nd->ch[i]=1; vc.eb(mp(it->F, num), i); } it++; } nd->l.erase(nd->l.begin(), it); if(vc.size()==0)return; if(!nd->lc)nd->lc=new NODE(); for(auto i:vc)upd_ins(nd->lc, s, (s+e)/2, i.F, nd->rv[i.S]); } void push_lft(NODE *nd, int s, int e, int num){ if(nd->l.size()==0)return; if(nd->l.begin()->F>num)return; auto it=nd->l.begin(); auto it2=nd->l.begin(); it2++; while(it2!=nd->l.end()){ if(it2->F>num)break; if(it->S.size()>it2->S.size())swap(it->S, it2->S); for(auto i:it->S){ nd->ufl.mergepar(i, it2->S.back()); it2->S.eb(i); } it++; it2++; } nd->lnum[nd->ufl.findpar(it->S.back())]=num; swap(it->S, nd->l[num]); nd->l.erase(nd->l.begin(), nd->l.find(num)); } void push_rgt(NODE *nd, int s, int e, int num){ if(nd->r.size()==0)return; if(nd->r.rbegin()->F<num)return; auto it=nd->r.end(); auto it2=nd->r.end(); it--; it2--; if(it2!=nd->r.begin())it2--; while(it!=nd->r.begin()){ if(it2->F<num)break; if(it->S.size()>it2->S.size())swap(it->S, it2->S); for(auto i:it->S){ nd->ufr.mergepar(i, it2->S.back()); it2->S.eb(i); } it--; it2--; } nd->rnum[nd->ufr.findpar(it->S.back())]=num; swap(it->S, nd->r[num]); nd->r.erase(++(nd->r.find(num)), nd->r.end()); } void upd_ins(NODE *nd, int s, int e, pii rn, int num){ int mid=(s+e)/2; if((rn.F<=mid&&mid<rn.S)||s==e){ nd->ins(s, e, rn, num); return; } if(rn.S<=mid){ if(!nd->lc)nd->lc=new NODE(); upd_ins(nd->lc, s, (s+e)/2, rn, num); } else{ if(!nd->rc)nd->rc=new NODE(); upd_ins(nd->rc, (s+e)/2+1, e, rn, num); } } void upd_swpl(NODE *nd, int s, int e, int num){ if(s==e)return; int mid=(s+e)/2; if(num>mid){ overkill_lft(nd, s, e, num); if(nd->rc)upd_swpl(nd->rc, (s+e)/2+1, e, num); } else{ push_lft(nd, s, e, num); if(nd->lc)upd_swpl(nd->lc, s, (s+e)/2, num); } } void upd_swpr(NODE *nd, int s, int e, int num){ if(s==e)return; int mid=(s+e)/2; if(num<=mid){ overkill_rgt(nd, s, e, num); if(nd->lc)upd_swpr(nd->lc, s, (s+e)/2, num); } else{ push_rgt(nd, s, e, num); if(nd->rc)upd_swpr(nd->rc, (s+e)/2+1, e, num); } } void upd_ins(pii rn, int num){ rn.S=n-rn.S; upd_ins(rt, 0, n, rn, num); } void upd_swpl(int num){upd_swpl(rt, 0, n, num);} void upd_swpr(int num){upd_swpr(rt, 0, n, num);} pii query(int num){ pii tmp=query(rt, 0, n, num); tmp.S=n-tmp.S; return tmp; } }seg; int main(){ scanf("%d %d %d", &n, &m, &q); for(int i=1; i<=m; i++){ int a, b; scanf("%d %d", &a, &b); seg.upd_ins(mp(a, b), ++re); } for(int i=1; i<=q; i++){ int a; scanf("%d", &a); if(a==1){ int b; scanf("%d", &b); pii ans=seg.query(b); printf("??? %d %d\n", ans.F, ans.S); } if(a==2){ int b; scanf("%d", &b); seg.upd_swpl(n-b); } if(a==3){ int b; scanf("%d", &b); seg.upd_swpr(b); } if(a==4){ int b, c; scanf("%d %d", &b, &c); seg.upd_ins(mp(b, c), ++re); } } }

Compilation message (stderr)

sweeping.cpp: In function 'int main()':
sweeping.cpp:179:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
sweeping.cpp:187:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~
sweeping.cpp:190:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b);
             ~~~~~^~~~~~~~~~
sweeping.cpp:196:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b);
             ~~~~~^~~~~~~~~~
sweeping.cpp:201:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b);
             ~~~~~^~~~~~~~~~
sweeping.cpp:206:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &b, &c);
             ~~~~~^~~~~~~~~~~~~~~~~
#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...