Submission #916989

#TimeUsernameProblemLanguageResultExecution timeMemory
916989MilosMilutinovicSweeping (JOI20_sweeping)C++14
65 / 100
7248 ms607636 KiB
#include<bits/stdc++.h> #define pb push_back #define fi first #define se second #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef long double ld; template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;} template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;} ll readint(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,q; int v[1500005][2],fa[1500005],ch[1500005][2],tag[1500005][2],prior[1500005]; mt19937 rng(time(0)); void make(int id){ tag[id][0]=tag[id][1]=-1; prior[id]=rng(); fa[id]=ch[id][0]=ch[id][1]=0; } void pushdown(int id){ if(!id) return; for(int i=0;i<2;i++){ if(tag[id][i]==-1) continue; for(int j=0;j<2;j++){ if(ch[id][j]==0) continue; v[ch[id][j]][i]=tag[id][i]; tag[ch[id][j]][i]=tag[id][i]; } tag[id][i]=-1; } } void split(int id,int&l,int&r,int a,int b,int idx){ if(!id) return (void)(l=r=0); pushdown(id); if(v[id][0]<=a&&v[id][1]<=b&&(mp(v[id][0],v[id][1])!=mp(a,b)||id<idx)){ fa[ch[id][1]]=0; split(ch[id][1],ch[id][1],r,a,b,idx); l=id; fa[ch[id][1]]=id; }else{ fa[ch[id][0]]=0; split(ch[id][0],l,ch[id][0],a,b,idx); r=id; fa[ch[id][0]]=id; } } void merge(int&id,int l,int r){ if(!l) return (void)(id=r); if(!r) return (void)(id=l); pushdown(l); pushdown(r); if(prior[l]>prior[r]) swap(l,r); int L=0,R=0; split(l,L,R,v[r][0],v[r][1],r); fa[ch[r][0]]=0; fa[ch[r][1]]=0; merge(ch[r][0],ch[r][0],L); merge(ch[r][1],ch[r][1],R); fa[ch[r][0]]=r; fa[ch[r][1]]=r; id=r; pushdown(id); } namespace segtree{ int root,tsz,ls[10000005],rs[10000005]; map<int,multiset<pii>> ids; pii mini[10000005]; void modify(int&id,int l,int r,int i,pii v){ if(!id) id=++tsz,mini[id]=mp(n+1,0); if(l==r) return (void)(mini[id]=v); int mid=(l+r)/2; if(i<=mid) modify(ls[id],l,mid,i,v); else modify(rs[id],mid+1,r,i,v); mini[id]=mp(n+1,0); if(ls[id]) mini[id]=min(mini[id],mini[ls[id]]); if(rs[id]) mini[id]=min(mini[id],mini[rs[id]]); } pii query(int id,int l,int r,int ql,int qr){ if(!id||l>r||l>qr||r<ql) return mp(n+1,0); if(ql<=l&&r<=qr) return mini[id]; int mid=(l+r)/2; return min(query(ls[id],l,mid,ql,qr),query(rs[id],mid+1,r,ql,qr)); } void add(int x,int y,int i){ ids[x].emplace(y,i); modify(root,0,n,x,*ids[x].begin()); } void rem(int x,int y,int i){ if(ids[x].find(mp(y,i))==ids[x].end()) while(true){} ids[x].erase(ids[x].find(mp(y,i))); modify(root,0,n,x,(ids[x].empty()?mp(n+1,0):*ids[x].begin())); } pii get(int l,int r){ return query(root,0,n,l,r); } }; vector<int> find(int l){ vector<int> ret; while(true){ pii mn=segtree::get(0,l); if(mn.fi>n-l) break; int i=mn.se; segtree::rem(v[i][0],v[i][1],i); while(fa[i]) i=fa[i]; ret.pb(i); } return ret; } int godown(int id){ if(!ch[id][0]) return id; else return godown(ch[id][0]); } int main(){ n=readint(); m=readint(); q=readint(); for(int i=1;i<=m;i++) for(int j=0;j<2;j++) v[i][j]=readint(); for(int i=1;i<=m;i++) make(i),segtree::add(v[i][0],v[i][1],i); while(q--){ int t=readint(); if(t==1){ int i=readint(); vector<int> anc; for(int v=i;v;v=fa[v]) anc.pb(v); reverse(anc.begin(),anc.end()); for(int v:anc) pushdown(v); printf("%d %d\n",v[i][0],v[i][1]); } if(t==2){ int l=readint(); int root=0; vector<int> ids=find(n-l); for(int i:ids){ int L=0,R=0; split(i,L,R,n-l,l,1e9); if(R!=0){ int x=godown(R); vector<int> anc; for(int v=x;v;v=fa[v]) anc.pb(v); reverse(anc.begin(),anc.end()); for(int v:anc) pushdown(v); segtree::add(v[x][0],v[x][1],x); } v[L][0]=n-l; tag[L][0]=n-l; pushdown(L); merge(root,root,L); pushdown(root); } if(root!=0){ int x=godown(root); vector<int> anc; for(int v=x;v;v=fa[v]) anc.pb(v); reverse(anc.begin(),anc.end()); for(int v:anc) pushdown(v); segtree::add(v[x][0],v[x][1],x); } } if(t==3){ int l=readint(); int root=0; vector<int> ids=find(l); for(int i:ids){ int L=0,R=0; split(i,L,R,l,n-l,1e9); if(R!=0){ int x=godown(R); vector<int> anc; for(int v=x;v;v=fa[v]) anc.pb(v); reverse(anc.begin(),anc.end()); for(int v:anc) pushdown(v); segtree::add(v[x][0],v[x][1],x); } v[L][1]=n-l; tag[L][1]=n-l; pushdown(L); pushdown(R); merge(root,root,L); pushdown(root); } if(root!=0){ int x=godown(root); vector<int> anc; for(int v=x;v;v=fa[v]) anc.pb(v); reverse(anc.begin(),anc.end()); for(int v:anc) pushdown(v); segtree::add(v[x][0],v[x][1],x); } } if(t==4){ make(++m); for(int j=0;j<2;j++) v[m][j]=readint(); segtree::add(v[m][0],v[m][1],m); } } 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...