Submission #304529

#TimeUsernameProblemLanguageResultExecution timeMemory
304529oleh1421Comparing Plants (IOI20_plants)C++17
5 / 100
425 ms39812 KiB
#define SYS #ifdef SYS #include "plants.h" #endif // SYS #include <bits/stdc++.h> typedef long long ll; using namespace std; const int N=300010; struct node{ int mx,l,r,best; }; node t[N*4]; int w[N*4]; int a[N]; int p[N]; int nn,kk; node Merge(node A,node B){ if (A.mx>B.mx) { return A; } if (A.mx<B.mx) { return B; } node C; C.mx=A.mx; C.l=A.l; C.r=B.r; if (A.best!=-1) C.best=A.best; else if (B.best!=-1) C.best=B.best; else if (B.l>=A.r+kk) C.best=B.l; else C.best=-1; return C; } void build(int v,int l,int r){ if (l>r) return; w[v]=0; t[v].best=-1; if (l==r){ t[v].mx=a[l]; t[v].l=t[v].r=l; t[v].best=-1; return; } int m=(l+r)/2; build(v+v,l,m); build(v+v+1,m+1,r); t[v]=Merge(t[v+v],t[v+v+1]); } void push(int v){ t[v+v].mx+=w[v]; t[v+v+1].mx+=w[v]; w[v+v]+=w[v]; w[v+v+1]+=w[v]; w[v]=0; } void upd(int v,int l,int r,int L,int R,int x){ if (l>R || r<L) return; if (l>=L && r<=R){ t[v].mx+=x; w[v]+=x; return; } push(v); int m=(l+r)/2; upd(v+v,l,m,L,R,x); upd(v+v+1,m+1,r,L,R,x); t[v]=Merge(t[v+v],t[v+v+1]); } void add(int n,int l,int r,int x){ if (l<=r){ upd(1,0,n-1,l,r,x); } else { upd(1,0,n-1,l,n-1,x); upd(1,0,n-1,0,r,x); } } int go1[N]; int go2[N]; int rp[N]; pair<int,int>t1[N*4]; void upd1(int v,int l,int r,int pos,int x){ if (l==r){ t1[v]={x,l}; return; } int m=(l+r)/2; if (pos<=m) upd1(v+v,l,m,pos,x); else upd1(v+v+1,m+1,r,pos,x); t1[v]=max(t1[v+v],t1[v+v+1]); } pair<int,int> get1(int v,int l,int r,int L,int R){ if (l>R || r<L) return {-1,-1}; if (l>=L && r<=R) return t1[v]; int m=(l+r)/2; return max(get1(v+v,l,m,L,R),get1(v+v+1,m+1,r,L,R)); } int get_pos(int n,int l,int r){ pair<int,int>cur; if (l<=r){ cur=get1(1,0,n-1,l,r); } else { cur=max(get1(1,0,n-1,0,r),get1(1,0,n-1,l,n-1)); } if (cur.first<=0) return -1; return cur.second; } vector<int>g[N]; int L[N]; int R[N]; int go_1(int x){ if (go1[x]==x) return x; return go1[x]=go_1(go1[x]); } int go_2(int x){ if (go2[x]==x) return x; return go2[x]=go_2(go2[x]); } void init(int k, std::vector<int> r) { int n=r.size(); nn=n; kk=k; for (int i=0;i<n;i++){ L[i]=R[i]=-1; } for (int &i:r){ i=k-i-1; } for (int i=0;i<n;i++) a[i]=r[i]; build(1,0,n-1); for (int cur=n;cur>=1;cur--){ if (t[1].mx>k-1) exit(1); int pos=(t[1].best==-1 ? t[1].l : t[1].best); p[pos]=cur; rp[cur]=pos; // cout<<pos<<endl; add(n,(pos-k+1+n)%n,pos,1); add(n,pos,pos,-n*3); } for (int cur=1;cur<=n;cur++){ int pos=rp[cur]; int nxt1=get_pos(n,pos,(pos+k-1)%n); if (nxt1==-1) nxt1=pos; go1[pos]=nxt1; int nxt2=get_pos(n,(pos-k+1+n)%n,pos); if (nxt2==-1) nxt2=pos; go2[pos]=nxt2; upd1(1,0,n-1,pos,cur); if (nxt1!=pos) { g[pos].push_back(nxt1); // cout<<pos<<" "<<nxt1<<endl; } if (nxt2!=pos) { g[pos].push_back(nxt2); // cout<<pos<<" "<<nxt2<<endl; } } return; } int compare_plants(int x, int y) { int mult=1; if (x>y){ swap(x,y); mult=-1; } if (p[x]>p[y]){ if (go_1(x)>=y || go_1(x)<x) return mult; if (go_2(x)<=y && go_2(x)>x) return mult; return 0; } else { if (go_1(y)>=x && go_1(y)<y) return -mult; if (go_2(y)<=x || go_2(y)>y) return -mult; return 0; } return 0; } #ifndef SYS #include <cstdio> #include <cassert> #include <vector> static int n, k, q; static std::vector<int> r; static std:: vector<int> x; static std:: vector<int> y; static std:: vector<int> answer; int main() { assert(scanf("%d%d%d", &n, &k, &q) == 3); r.resize(n); answer.resize(q); for (int i = 0; i < n; i++) { int value; assert(scanf("%d", &value) == 1); r[i] = value; } x.resize(q); y.resize(q); for (int i = 0; i < q; i++) { assert(scanf("%d%d", &x[i], &y[i]) == 2); } fclose(stdin); init(k, r); for (int i = 0; i < q; i++) { answer[i] = compare_plants(x[i], y[i]); } for (int i = 0; i < q; i++) { printf("%d\n", answer[i]); } fclose(stdout); return 0; } #endif /* 4 3 2 0 1 1 2 0 2 1 2 */
#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...