Submission #916557

#TimeUsernameProblemLanguageResultExecution timeMemory
916557MilosMilutinovicSweeping (JOI20_sweeping)C++14
0 / 100
1824 ms2097152 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(); } 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]) 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){ if(!id) return (void)(l=r=0); pushdown(id); if(v[id][0]<=a&&v[id][1]<=b){ fa[ch[id][1]]=0; split(ch[id][1],ch[id][1],r,a,b); l=id; fa[ch[id][1]]=id; }else{ fa[ch[id][0]]=0; split(ch[id][0],l,ch[id][0],a,b); 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]); 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(L); pushdown(R); pushdown(id); } 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); while(q--){ int t=readint(); if(t==1){ int i=readint(); vector<int> anc; for(int v=i,iter=0;v;v=fa[v],iter++) assert(iter<=5000),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; for(int i=1;i<=m;i++){ if(fa[i]) continue; int L=0,R=0; split(i,L,R,n-l,l); v[L][0]=n-l; tag[L][0]=n-l; pushdown(L); pushdown(R); fa[L]=fa[R]=0; merge(root,root,L); pushdown(root); fa[root]=0; } } if(t==3){ int l=readint(); int root=0; for(int i=1;i<=m;i++){ if(fa[i]) continue; int L=0,R=0; split(i,L,R,l,n-l); v[L][1]=n-l; tag[L][1]=n-l; pushdown(L); pushdown(R); fa[L]=fa[R]=0; merge(root,root,L); pushdown(root); fa[root]=0; } } if(t==4){ make(++m); for(int j=0;j<2;j++) v[m][j]=readint(); } } 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...