Submission #622711

#TimeUsernameProblemLanguageResultExecution timeMemory
622711leakedComparing Plants (IOI20_plants)C++17
27 / 100
706 ms46208 KiB
#include <bits/stdc++.h> #define f first #define s second #define vec vector #define pb push_back #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define pw(x) (1LL<<(x)) #define sz(x) (int)(x).size() #define m_p make_pair #define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long ll; typedef pair<int,int> pii; template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);} template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);} const int N=2e5+1; struct segtree{ pii t[4*N]; int p[4*N]; vec<int> a; void push(int v,int tl,int tr){ for(auto &u : {v<<1,v<<1|1}){ t[u].f+=p[v]; p[u]+=p[v]; } p[v]=0; } void build(int v,int tl,int tr){ p[v]=0; if(tl==tr){ t[v]={a[tl],tl}; } else{ int tm=(tl+tr)>>1; build(v<<1,tl,tm);build(v<<1|1,tm+1,tr); t[v]=min(t[v<<1],t[v<<1|1]); } } void add(int l,int r,int x,int v,int tl,int tr){ if(tl>=l&&tr<=r){ t[v].f+=x;p[v]+=x; // cout<<tl<<' '<<tr<<' '<<x<<endl; return; } if(tl>r||tr<l) return; int tm=(tl+tr)>>1;push(v,tl,tr); add(l,r,x,v<<1,tl,tm);add(l,r,x,v<<1|1,tm+1,tr); t[v]=min(t[v<<1],t[v<<1|1]); } pii get(int l,int r,int v,int tl,int tr){ if(tl>=l&&tr<=r) return t[v]; if(tl>r||tr<l) return m_p(1e9,-1); int tm=(tl+tr)>>1;push(v,tl,tr); return min(get(l,r,v<<1,tl,tm),get(l,r,v<<1|1,tm+1,tr)); } }sega; int n,k; int h[N],it=0; int _find(int i){ pii c; if((i-k+1)<0){ int r=k-(i+1); c=sega.get(n-r,n-1,1,0,n-1); if(c.f>0){ c=sega.get(0,i-1,1,0,n-1); } } else{ c=sega.get(i-k+1,i-1,1,0,n-1); } return (c.f<=0?c.s:-1); } int ht[N]; void place(int i){ sega.add(i,i,1e9,1,0,n-1); int j=_find(i); // cout<<"PLACE "<<i<<endl; while(j!=-1){ place(j); j=_find(i); } ht[i]=it++; if((i-k+1)<0){ int r=k-(i+1); sega.add(n-r,n-1,-1,1,0,n-1); sega.add(0,i,-1,1,0,n-1); } else{ sega.add(i-k+1,i,-1,1,0,n-1); } } int lft[N][20],rgt[N][20]; void init(int k, std::vector<int> r){ n=sz(r);::k=k; sega.a=r; sega.build(1,0,n-1); fill(ht,ht+n,-1); while(1){ pii c=sega.t[1]; if(c.f>0){ break; } int j=c.s; place(j); } for(int i=0;i<n;i++) ht[i]=n-ht[i]+1; vec<int> ids(n); sort(all(ids),[&](int i,int j){return ht[i]<ht[j];}); const int inf=(int)(1e9)-1; for(int i=0;i<n;i++) sega.a[i]=inf; sega.build(1,0,n-1); for(auto &i : ids){ pii c=((i+1)>=k?sega.get(i-k+1,i-1,1,0,n-1):min(sega.get(0,i-1,1,0,n-1),sega.get(n-(k-(i+1)),n-1,1,0,n-1))); if(c.f>=inf) lft[i][0]=0; else lft[i][0]=(i+n-c.s)%n; c=(i+k-1<n?sega.get(i+1,i+k-1,1,0,n-1):min(sega.get(i+1,n-1,1,0,n-1),sega.get(0,k-(n-i)-1,1,0,n-1))); if(c.f>=inf) rgt[i][0]=0; else rgt[i][0]=(c.s-i+n)%n; sega.add(i,i,-inf-ht[i],1,0,n-1); } for(int i=1;i<20;i++){ for(int j=0;j<n;j++){ lft[j][i]=lft[j][i]+lft[(j+n-lft[j][i])%n][i]; rgt[j][i]=rgt[j][i]+rgt[(j+rgt[j][i])%n][i]; if(lft[j][i]>n) lft[j][i]=0; if(rgt[j][i]>n) rgt[j][i]=0; } } } int compare_plants(int x, int y){ int z=x; for(int i=19;i>=0;i--){ if(rgt[z][i]<(y-z+n)%n) z=(z+rgt[z][i])%n; } if(ht[z]>ht[y] && (y-z+n)%n<k) return 1; z=y; for(int i=19;i>=0;i--){ if(rgt[z][i]<(x-z+n)%n) z=(z+rgt[z][i])%n; } if(ht[z]>ht[x] && (x-z+n)%n<k) return -1; z=y; for(int i=19;i>=0;i--){ if(lft[z][i]<(z-x+n)%n) z=(z-lft[z][i]+n)%n; } if(ht[z]>ht[x] && (z-x+n)%n<k) return -1; z=x; for(int i=19;i>=0;i--){ if(lft[z][i]<(z-y+n)%n) z=(z-lft[z][i]+n)%n; } if(ht[z]>ht[y] && (z-y+n)%n<k) return 1; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...