Submission #415016

#TimeUsernameProblemLanguageResultExecution timeMemory
415016MKopchevComparing Plants (IOI20_plants)C++14
0 / 100
67 ms4280 KiB
#include "plants.h" #include<bits/stdc++.h> using namespace std; const int nmax=2e5+42; int my_n,my_k; int inp[nmax]; struct info { int mini,lazy; int pos; }; info tree[4*nmax]; void push(int node) { tree[node*2].lazy+=tree[node].lazy; tree[node*2+1].lazy+=tree[node].lazy; tree[node].lazy=0; } info actual(info a) { a.mini+=a.lazy; a.lazy=0; return a; } info my_merge(info a,info b) { a=actual(a); b=actual(b); if(a.mini<=b.mini)return a; return b; } void build(int node,int l,int r) { if(l==r) { tree[node].mini=inp[l]; tree[node].lazy=0; tree[node].pos=l; return; } int av=(l+r)/2; build(node*2,l,av); build(node*2+1,av+1,r); tree[node]=my_merge(tree[node*2],tree[node*2+1]); } void update(int node,int l,int r,int lq,int rq,int val) { if(l==lq&&r==rq) { tree[node].lazy+=val; return; } push(node); int av=(l+r)/2; if(lq<=av)update(node*2,l,av,lq,min(av,rq),val); if(av<rq)update(node*2+1,av+1,r,max(av+1,lq),rq,val); tree[node]=my_merge(tree[node*2],tree[node*2+1]); } int outp[nmax]; void init(int k, std::vector<int> r) { my_n=r.size(); my_k=k; for(int i=1;i<=my_n;i++)inp[i]=r[i-1]; build(1,1,my_n); for(int i=1;i<=my_n;i++) { info cur=actual(tree[1]); int pos=cur.pos; //cout<<"pos= "<<pos<<endl; outp[pos]=my_n-i; update(1,1,my_n,pos,pos,1e9); int l=pos-(k-1); int r=pos-1; if(1<=l)update(1,1,my_n,l,r,-1); else { l=l+my_n; update(1,1,my_n,l,my_n,-1); if(r>=1)update(1,1,my_n,1,r,-1); } } //for(int i=1;i<=my_n;i++)printf("%i ",outp[i]);printf("\n"); } int compare_plants(int x, int y) { x++; y++; if(outp[x]>outp[y])return 1; return -1; } /* 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; } */
#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...