Submission #613883

#TimeUsernameProblemLanguageResultExecution timeMemory
613883Koosha_mvComparing Plants (IOI20_plants)C++14
100 / 100
1573 ms145424 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; #define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl #define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl #define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define all(v) v.begin(),v.end() #define bit(n,k) (((n)>>(k))&1) #define Add(x,y) x=(x+y)%mod #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first const int N=2e5+99,lg=20; int n,k,p[N],a[N],pos[N],seg[N<<2],lz[N<<2]; vector<int> vec; set<int> s,ok; pair<int,ll> A[lg][N],B[lg][N]; void check(int x){ int len; if(x==*s.begin()){ len=x-(*s.rbegin())+n; } else{ len=x-(*prev(s.lower_bound(x))); } if(len>=k){ ok.insert(x); } else{ if(ok.find(x)!=ok.end()){ ok.erase(x); } } } void adds(int x){ s.insert(x); check(x); if(x==*s.rbegin()){ check(*s.begin()); } else{ check(*s.upper_bound(x)); } } void dels(int x){ s.erase(x); if(*s.rbegin()<x){ check(*s.begin()); } else{ check(*s.upper_bound(x)); } } void upd(int id){ seg[id]=min(seg[id<<1],seg[id<<1|1]); } void shift(int id){ lz[id<<1]+=lz[id]; lz[id<<1|1]+=lz[id]; seg[id<<1]+=lz[id]; seg[id<<1|1]+=lz[id]; lz[id]=0; } void build(int id=1,int l=0,int r=n){ if(l+1==r){ seg[id]=p[l]; return ; } int mid=(l+r)>>1; build(id<<1,l,mid); build(id<<1|1,mid,r); upd(id); } void prt(int L,int R,int id=1,int l=0,int r=n){ if(seg[id]>1 || r<=L || R<=l) return ; if(l+1==r){ vec.pb(l); adds(l); return ; } int mid=(l+r)>>1; shift(id); prt(L,R,id<<1,l,mid); prt(L,R,id<<1|1,mid,r); upd(id); } void add(int L,int R,int val,int id=1,int l=0,int r=n){ if(r<=L || R<=l) return ; if(L<=l && r<=R){ lz[id]+=val; seg[id]+=val; return ; } int mid=(l+r)>>1; shift(id); add(L,R,val,id<<1,l,mid); add(L,R,val,id<<1|1,mid,r); upd(id); } void builda(){ build(); f(i,0,n){ if(p[i]==0){ s.insert(i); } } f(i,0,n){ if(p[i]==0){ add(i,i+1,n+10); check(i); } } f_(T,n-1,0){ int x=(*ok.begin()); //eror(x); ok.erase(x); a[x]=T; if(T==0) break ; int l=(x-k+n+1)%n,r=x; vec.clear(); if(r<l){ prt(0,r); prt(l,n); add(0,r,-1); add(l,n,-1); } else{ prt(l,r); add(l,r,-1); } dels(x); for(auto g : vec) add(g,g+1,n+10); } f(i,0,n) pos[a[i]]=i; } void AB(){ set<int> s; f(i,0,k-1) s.insert(a[i]); f_(i,n-1,0){ int ida=-1,idb=-1; if(*s.begin()<a[i]){ ida=pos[*prev(s.lower_bound(a[i]))]; } if(*s.rbegin()>a[i]){ idb=pos[*s.lower_bound(a[i])]; } s.insert(a[i]); s.erase(a[(i+k-1)%n]); if(ida==-1){ A[0][i]={i,0}; } else{ A[0][i]={ida,(ida-i+n)%n}; } if(idb==-1){ B[0][i]={i,0}; } else{ B[0][i]={idb,(idb-i+n)%n}; } } f(l,1,lg){ f(i,0,n){ A[l][i]={A[l-1][A[l-1][i].F].F,A[l-1][i].S+A[l-1][A[l-1][i].F].S}; B[l][i]={B[l-1][B[l-1][i].F].F,B[l-1][i].S+B[l-1][B[l-1][i].F].S}; } } } bool checkA(int u,int v){ int len=(v-u+n)%n; f_(l,lg-1,0){ if(A[l][u].S<=len){ len-=A[l][u].S; u=A[l][u].F; } } if((v-u+n)%n<k && a[u]>=a[v]) return 1; return 0; } bool checkB(int u,int v){ int len=(v-u+n)%n; f_(l,lg-1,0){ if(B[l][u].S<=len){ len-=B[l][u].S; u=B[l][u].F; } } if((v-u+n)%n<k && a[u]<=a[v]) return 1; return 0; } void init(int _k,vector<int> _p) { n=_p.size(),k=_k; f(i,0,n) p[i]=_p[i]; builda(); AB(); } int compare_plants(int x, int y) { if(checkA(x,y) || checkB(y,x)) return 1; if(checkB(x,y) || checkA(y,x)) 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...