Submission #721265

#TimeUsernameProblemLanguageResultExecution timeMemory
721265bin9638Comparing Plants (IOI20_plants)C++17
100 / 100
2096 ms167160 KiB
#include <bits/stdc++.h> #ifndef SKY #include "plants.h" #endif // SKY using namespace std; #define N 400010 #define ll long long #define fs first #define sc second #define ii pair<int,int> #define pb push_back int dem,k,n,h[N],a[N],pre[N][21],nxt[N][21]; ll dis_pre[N][21],dis_nxt[N][21]; int LOG; struct IT { struct node { ii min_val,max_val; int t=0; }ST[N*4]; void down(int id) { ST[id*2].min_val.fs+=ST[id].t; ST[id*2].max_val.fs+=ST[id].t; ST[id*2].t+=ST[id].t; ST[id*2+1].min_val.fs+=ST[id].t; ST[id*2+1].max_val.fs+=ST[id].t; ST[id*2+1].t+=ST[id].t; ST[id].t=0; } void update(int id,int l,int r,int i,ii val) { if(l>i||r<i) return; if(l==r) { ST[id].min_val=ST[id].max_val=val; return; } down(id); int mid=(l+r)/2; update(id*2,l,mid,i,val); update(id*2+1,mid+1,r,i,val); ST[id].min_val=min(ST[id*2].min_val,ST[id*2+1].min_val); ST[id].max_val=max(ST[id*2].max_val,ST[id*2+1].max_val); } void them(int id,int l,int r,int u,int v,int val) { if(l>r||l>v||r<u) return; if(l>=u&&r<=v) { ST[id].t+=val; ST[id].min_val.fs+=val; ST[id].max_val.fs+=val; return; } down(id); int mid=(l+r)/2; them(id*2,l,mid,u,v,val); them(id*2+1,mid+1,r,u,v,val); ST[id].min_val=min(ST[id*2].min_val,ST[id*2+1].min_val); ST[id].max_val=max(ST[id*2].max_val,ST[id*2+1].max_val); } ii get_min(int id,int l,int r,int u,int v) { if(l>v||r<u) return {1e9,-1}; if(l>=u&&r<=v) return ST[id].min_val; down(id); int mid=(l+r)/2; return min(get_min(id*2,l,mid,u,v),get_min(id*2+1,mid+1,r,u,v)); } ii get_max(int id,int l,int r,int u,int v) { if(l>v||r<u) return {-1e9,-1}; if(l>=u&&r<=v) return ST[id].max_val; down(id); int mid=(l+r)/2; return max(get_max(id*2,l,mid,u,v),get_max(id*2+1,mid+1,r,u,v)); } }T; void build(int i) { while(T.get_min(1,1,n*2,i+1+n-k+1,i+1+n-1).fs==0) { build(T.get_min(1,1,n*2,i+1+n-k+1,i+1+n-1).sc); } T.them(1,1,n*2,i+1+n-k+1,i+1+n-1,-1); if(i-k+1>=0) { T.them(1,1,n*2,i+1-k+1,i+1-1,-1); }else { T.them(1,1,n*2,1,i+1-1,-1); T.them(1,1,n*2,n*2-(k-i-2),n*2,-1); } T.update(1,1,n*2,i+1,{1e9,i}); T.update(1,1,n*2,i+n+1,{1e9,i}); h[i]=--dem; } void init(int cc, vector<int> r) { k=cc; n=r.size(); for(int i=0;i<n;i++) { a[i]=r[i]; T.update(1,1,n*2,i+1,{a[i],i}); T.update(1,1,n*2,i+n+1,{a[i],i}); } dem=n; while(T.get_min(1,1,n*2,1,n*2).fs==0) { build(T.get_min(1,1,n*2,1,n*2).sc); } // for(int i=0;i<n;i++)cout<<h[i]<<" "; for(int i=0;i<n;i++) { T.update(1,1,n*2,i+1,{-1e9,-1}); T.update(1,1,n*2,i+n+1,{-1e9,-1}); } vector<ii>s; for(int i=0;i<n;i++) s.pb({h[i],i}); sort(s.begin(),s.end()); memset(pre,-1,sizeof(pre)); memset(nxt,-1,sizeof(nxt)); for(auto cc:s) { int i=cc.sc; pre[i][0]=T.get_max(1,1,n*2,i+1+n-k+1,i+1+n-1).sc; nxt[i][0]=T.get_max(1,1,n*2,i+1+1,i+1+k-1).sc; int vt=T.get_max(1,1,n*2,i+1+n-k+1,i+1+n-1).sc; if(vt!=-1) { dis_pre[i][0]=(vt<=i ? i-vt :i+n-vt); } vt=T.get_max(1,1,n*2,i+1+1,i+1+k-1).sc; if(vt!=-1) { dis_nxt[i][0]=(vt>=i ? vt-i : vt+n-i); } T.update(1,1,n*2,i+1,cc); T.update(1,1,n*2,i+n+1,cc); //cout<<i<<" "<<pre[i][0]<<" "<<nxt[i][0]<<endl; } LOG=log2(n); for(int k=1;k<=LOG;k++) for(int i=0;i<n;i++) { pre[i][k]=(pre[i][k-1]==-1 ? -1 : pre[pre[i][k-1]][k-1]); nxt[i][k]=(nxt[i][k-1]==-1 ? -1 :nxt[nxt[i][k-1]][k-1]); dis_pre[i][k]=(pre[i][k-1]==-1 ? 1e9 : dis_pre[i][k-1]+dis_pre[pre[i][k-1]][k-1]); dis_nxt[i][k]=(nxt[i][k-1]==-1 ? 1e9 : dis_nxt[i][k-1]+dis_nxt[nxt[i][k-1]][k-1]); } } bool check(int x,int y) { LOG=log2(n); if(x<y) { int vt=x,dis=x+n-y; for(int k=LOG;k>=0;k--) if(pre[vt][k]!=-1&&dis_pre[vt][k]<=dis) { dis-=dis_pre[vt][k]; vt=pre[vt][k]; } if(dis<=k-1&&h[vt]>=h[y]) return 1; vt=x; dis=y-x; for(int k=LOG;k>=0;k--) if(nxt[vt][k]!=-1&&dis_nxt[vt][k]<=dis) { dis-=dis_nxt[vt][k]; vt=nxt[vt][k]; } if(dis<=k-1&&h[vt]>=h[y]) return 1; }else { int vt=x,dis=x-y; for(int k=LOG;k>=0;k--) if(pre[vt][k]!=-1&&dis_pre[vt][k]<=dis) { dis-=dis_pre[vt][k]; vt=pre[vt][k]; } if(dis<=k-1&&h[vt]>=h[y]) return 1; vt=x; dis=(y+n-x); for(int k=LOG;k>=0;k--) if(nxt[vt][k]!=-1&&dis_nxt[vt][k]<=dis) { dis-=dis_nxt[vt][k]; vt=nxt[vt][k]; } if(dis<=k-1&&h[vt]>=h[y]) return 1; } return 0; } int compare_plants(int x, int y) { if(check(x,y)) return 1; if(check(y,x)) return -1; return 0; } #ifdef SKY int main() { freopen("A.inp","r",stdin); freopen("A.out","w",stdout); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n,k; cin>>n>>k; vector<int>r(n); for(int i=0;i<n;i++) cin>>r[i];//,cout<<r[i]<<endl; init(k,r); int q; cin>>q; while(q--) { int x,y; cin>>x>>y; cout<<compare_plants(x,y)<<endl; } return 0; } #endif
#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...