Submission #893633

#TimeUsernameProblemLanguageResultExecution timeMemory
893633abcvuitunggioComparing Plants (IOI20_plants)C++17
44 / 100
472 ms17388 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; const int INF=1e9; struct T{ int mn,pos; }st[800001]; T operator +(T a, T b){ return (a.mn>b.mn?b:a); } int n,k,lazy[800001],p[200001],id; vector <int> a; void down(int node, int l, int r){ if (!lazy[node]||l==r) return; st[node<<1].mn+=lazy[node]; st[node<<1|1].mn+=lazy[node]; lazy[node<<1]+=lazy[node]; lazy[node<<1|1]+=lazy[node]; lazy[node]=0; } void build(int node, int l, int r){ if (l==r){ st[node]={a[l],l}; return; } int mid=(l+r)>>1; build(node<<1,l,mid); build(node<<1|1,mid+1,r); st[node]=st[node<<1]+st[node<<1|1]; } void update(int node, int l, int r, int u, int v, int val){ if (l>v||r<u||u>v) return; if (l>=u&&r<=v){ st[node].mn+=val; lazy[node]+=val; return; } down(node,l,r); int mid=(l+r)>>1; update(node<<1,l,mid,u,v,val); update(node<<1|1,mid+1,r,u,v,val); st[node]=st[node<<1]+st[node<<1|1]; } T get(int node, int l, int r, int u, int v){ if (l>v||r<u||u>v) return {INF,0}; if (l>=u&&r<=v) return st[node]; down(node,l,r); int mid=(l+r)>>1; return get(node<<1,l,mid,u,v)+get(node<<1|1,mid+1,r,u,v); } int calc(int j){ T t={INF,0}; if (j<k) t=get(1,0,n-1,0,j-1)+get(1,0,n-1,n+j-k+1,n-1); else t=get(1,0,n-1,j-k+1,j-1); if (t.mn) return -1; return t.pos; } void dfs(int i){ while (calc(i)!=-1) dfs(calc(i)); p[i]=id; id--; if (i<k){ update(1,0,n-1,0,i-1,-1); update(1,0,n-1,n+i-k+1,n-1,-1); } else update(1,0,n-1,i-k+1,i-1,-1); update(1,0,n-1,i,i,INF); } void init(int K, vector <int> r){ k=K; a=r; n=id=a.size(); build(1,0,n-1); while (!st[1].mn) dfs(st[1].pos); } int compare_plants(int x, int y){ return (p[x]>p[y]?1:(p[x]<p[y]?-1: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...