Submission #308393

#TimeUsernameProblemLanguageResultExecution timeMemory
308393gs18115Sweeping (JOI20_sweeping)C++14
10 / 100
9690 ms1866476 KiB
#include<iostream> #include<vector> #include<map> #include<algorithm> #define ep emplace #define eb emplace_back #define fi first #define se second #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef pair<int,int>pi; typedef pair<ll,ll>pl; const int inf=1e9+7; const ll INF=1e18; pi pos[1500010]; int ng[1500010],gl[1500010],gr[1500010]; struct seg { struct node { int ind,mid; vector<vector<int> >vl,vr; vector<int>lf,rg; map<int,int>mpl,mpr; vector<int>nl,nr; inline int ngl(int l) { int g; if(!nl.empty()) g=nl.back(),nl.pop_back(); else g=lf.size(),lf.eb(l),vl.eb(vector<int>()); lf[g]=l; return mpl[l]=g; } inline int ngr(int r) { int g; if(!nr.empty()) g=nr.back(),nr.pop_back(); else g=rg.size(),rg.eb(r),vr.eb(vector<int>()); rg[g]=r; return mpr[r]=g; } inline void dell(int g) { vl[g].clear(); vl[g].shrink_to_fit(); nl.eb(g); return; } inline void delr(int g) { vr[g].clear(); vr[g].shrink_to_fit(); nr.eb(g); return; } inline void put(int x) { ng[x]=ind; int cl=pos[x].fi; int cr=pos[x].se; { auto it=mpl.find(cl); if(it==mpl.end()) gl[x]=ngl(cl); else gl[x]=it->se; vl[gl[x]].eb(x); } { auto it=mpr.find(cr); if(it==mpr.end()) gr[x]=ngr(cr); else gr[x]=it->se; vr[gr[x]].eb(x); } return; } inline vector<int>pushl(int l) { if(l>mid) { vector<int>ret; auto it=mpr.end(); while(it!=mpr.begin()) { it--; if(it->fi<l) break; int grp=it->se; for(int&t:vr[grp]) if(ng[t]==ind) pos[t]=pi(l,rg[grp]),ret.eb(t); delr(grp); mpr.erase(it); it=mpr.end(); } return ret; } vector<int>gv; auto it=mpl.begin(); int ci=-1,csz=-1; while(it!=mpl.end()) { if(it->fi>l) break; int grp=it->se; if((int)vl[grp].size()>csz) csz=vl[ci=grp].size(); gv.eb(grp); mpl.erase(it); it=mpl.begin(); } if(ci==-1) return vector<int>(); lf[ci]=l; mpl[l]=ci; for(int&t:gv) { if(t==ci) continue; for(int&x:vl[t]) if(ng[x]==ind) vl[gl[x]=ci].eb(x); dell(t); } return vector<int>(); } inline vector<int>pushr(int r) { if(r<mid) { vector<int>ret; auto it=mpl.begin(); while(it!=mpl.end()) { if(it->fi>r) break; int grp=it->se; for(int&t:vl[grp]) if(ng[t]==ind) pos[t]=pi(lf[grp],r),ret.eb(t); dell(grp); mpl.erase(it); it=mpl.begin(); } return ret; } vector<int>gv; auto it=mpr.end(); int ci=-1,csz=-1; while(it!=mpr.begin()) { it--; if(it->fi<r) break; int grp=it->se; if((int)vl[grp].size()>csz) csz=vl[ci=grp].size(); gv.eb(grp); mpr.erase(it); it=mpr.end(); } if(ci==-1) return vector<int>(); rg[ci]=r; mpr[r]=ci; for(int&t:gv) { if(t==ci) continue; for(int&x:vr[t]) if(ng[x]==ind) vr[gr[x]=ci].eb(x); delr(t); } return vector<int>(); } }nd[6000010]; int tree[12000010]; int nct; inline int nnd(int m) { nct++; nd[nct].ind=nct; nd[nct].mid=m; return nct; } inline void init(int n,int s,int e) { if(s>e) return; int m=s+(e-s)/2; tree[n]=nnd(m); if(s==e) return; init(n*2,s,m-1); init(n*2+1,m+1,e); return; } void put(int n,int s,int e,int x) { int m=s+(e-s)/2; if(pos[x].se<m) return put(n*2,s,m-1,x); if(pos[x].fi>m) return put(n*2+1,m+1,e,x); nd[tree[n]].put(x); return; } void pushl(int n,int s,int e,int l) { if(l<=s||l>e) return; int m=s+(e-s)/2; vector<int>pv=nd[tree[n]].pushl(l); for(int&t:pv) put(n*2+1,m+1,e,t); pushl(n*2,s,m-1,l); pushl(n*2+1,m+1,e,l); return; } void pushr(int n,int s,int e,int r) { if(r<s||r>=e) return; int m=s+(e-s)/2; vector<int>pv=nd[tree[n]].pushr(r); for(int&t:pv) put(n*2,s,m-1,t); pushr(n*2,s,m-1,r); pushr(n*2+1,m+1,e,r); return; } inline pi print(int x) { return pi(nd[ng[x]].lf[gl[x]],nd[ng[x]].rg[gr[x]]); } }st; int pct; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n,m,q; cin>>n>>m>>q; vector<int>cpv; for(int i=0;i++<m;) { cin>>pos[i].fi>>pos[i].se; pos[i].se=n-pos[i].se; cpv.eb(pos[i].fi),cpv.eb(pos[i].se); } vector<pi>qv; pct=m; for(int i=0;i<q;i++) { int t,l; cin>>t>>l; if(t==2) cpv.eb(l=n-l); else if(t==3) cpv.eb(l); else if(t==4) { pos[++pct].fi=l; cin>>pos[pct].se; pos[pct].se=n-pos[pct].se; cpv.eb(pos[pct].fi),cpv.eb(pos[pct].se); } qv.eb(t,l); } sort(all(cpv)); cpv.erase(unique(all(cpv)),cpv.end()); for(int i=0;i++<pct;) pos[i].fi=lower_bound(all(cpv),pos[i].fi)-cpv.begin(), pos[i].se=lower_bound(all(cpv),pos[i].se)-cpv.begin(); int cn=cpv.size(); st.init(1,0,cn-1); for(int i=0;i++<m;) st.put(1,0,cn-1,i); pct=m; for(pi&t:qv) { if(t.fi==1) { pi p=st.print(t.se); cout<<cpv[p.fi]<<' '<<(n-cpv[p.se])<<'\n'; } else if(t.fi==2) st.pushl(1,0,cn-1,(int)(lower_bound(all(cpv),t.se)-cpv.begin())); else if(t.fi==3) st.pushr(1,0,cn-1,(int)(lower_bound(all(cpv),t.se)-cpv.begin())); else st.put(1,0,cn-1,++pct); } 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...