Submission #415091

#TimeUsernameProblemLanguageResultExecution timeMemory
415091MKopchevComparing Plants (IOI20_plants)C++14
49 / 100
604 ms24936 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; if(a.mini>b.mini)return b; if(b.pos-a.pos<=my_k-1)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]; set<int> zeros,legit; void test(int pos) { if(zeros.size()==1) { legit.insert(pos); return; } set<int>::iterator it=zeros.lower_bound(pos); if(it==zeros.begin())it=zeros.end(); it--; int prv=*it; if(prv>pos)prv=prv-my_n; //cout<<"testing "<<pos<<" : prv= "<<prv<<endl; if(pos-prv>=my_k)legit.insert(pos); } void add(int pos) { if(zeros.size()==0) { zeros.insert(pos); legit.insert(pos); return; } zeros.insert(pos); set<int>::iterator it=zeros.lower_bound(pos); it++; if(it==zeros.end())it=zeros.begin(); int nxt=*it; legit.erase(nxt); test(nxt); test(pos); } void sub(int pos) { legit.erase(pos); zeros.erase(pos); if(zeros.size()==0) { return; } set<int>::iterator it=zeros.lower_bound(pos); if(it==zeros.end())it=zeros.begin(); test(*it); } int pref[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]; for(int i=1;i<=my_n;i++)pref[i]=pref[i-1]+inp[i]; build(1,1,my_n); for(int i=1;i<=my_n;i++) { while(1) { info cur=actual(tree[1]); if(cur.mini)break; int pos=cur.pos; update(1,1,my_n,pos,pos,1e9); add(pos); } /* cout<<"i= "<<i<<endl; cout<<"zeros= ";for(auto w:zeros)cout<<w<<" ";cout<<endl; cout<<"legit= ";for(auto w:legit)cout<<w<<" ";cout<<endl; */ //cout<<"pos= "<<pos<<endl; int pos=*legit.begin(); sub(pos); outp[pos]=my_n-i; 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; //cout<<"other "<<l<<" "<<my_n<<" and "<<1<<" "<<r<<endl; 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(my_k==2) { if(pref[y-1]-pref[x-1]==y-x)return -1; if(pref[y-1]-pref[x-1]==0)return 1; if(pref[x-1]+pref[my_n]-pref[y-1]==my_n-y+x)return 1; if(pref[x-1]+pref[my_n]-pref[y-1]==0)return -1; return 0; } 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...