Submission #373404

#TimeUsernameProblemLanguageResultExecution timeMemory
373404pit4hComparing Plants (IOI20_plants)C++14
0 / 100
4054 ms19948 KiB
#include "plants.h" #include<bits/stdc++.h> #define st first #define nd second; #define mp make_pair using namespace std; using pii = pair<int, int>; const int MAXN = 2e5+1, base = (1<<18); int n, k, when[MAXN], nr; int ptr[MAXN], ptrr[MAXN]; vector<int> R; pii tree_max[2*base+1]; void upd(int x) { pii val = mp(when[x], x); x+=base; while(x) { tree_max[x] = max(tree_max[x], val); x/=2; } } pii find_max(int l, int r) { if(l>r) { return max(find_max(l, n-1), find_max(0, r)); } l+=base, r+=base; pii res = tree_max[l]; if(l!=r) res = max(res, tree_max[r]); while(l/2 != r/2) { if(l%2==0) res = max(res, tree_max[l+1]); if(r%2==1) res = max(res, tree_max[r-1]); l /= 2; r /= 2; } return res; } int tree[2*base+1], push[2*base+1]; void ADD(int id, int val) { tree[id] += val; push[id] += val; } void add(int l, int r, int val, int id=1, int rl=0, int rr=base-1) { if(l>r) { add(l, n-1, val), add(0, r, val); return; } if(l>rr || r<rl) return; if(l<=rl && r>=rr) { ADD(id, val); return; } ADD(id*2, push[id]), ADD(id*2+1, push[id]); push[id] = 0; add(l, r, val, id*2, rl, (rl+rr)/2), add(l, r, val, id*2+1, (rl+rr)/2+1, rr); tree[id] = min(tree[id*2], tree[id*2+1]); } int find_closest_zero(int l, int r, int id=1, int rl=0, int rr=base-1) { if(l>rr || r<rl || tree[id]>0) return -1; if(rl==rr) { return rl; } ADD(id*2, push[id]), ADD(id*2+1, push[id]); push[id] = 0; int rs = find_closest_zero(l, r, id*2+1, (rl+rr)/2+1, rr); if(rs!=-1) return rs; return find_closest_zero(l, r, id*2, rl, (rl+rr)/2); } int clw_dist(int x, int y) { return (x<=y)? y-x: n-(x-y); } void solve(int x) { //cerr<<"solve("<<x<<")\n"; int prv = -1; if(x>0) { prv = find_closest_zero(0, x-1); } if(x<n-1 && prv==-1) { prv = find_closest_zero(x+1, n-1); } if(prv != -1 && clw_dist(prv, x) < k) { //cerr<<"->"; solve(prv); } when[x] = ++nr; ptr[x] = find_max((x+1)%n, (x+k-1)%n).second; ptrr[x] = find_max((x-(k-1)+n)%n, (x-1+n)%n).second; add((x-k+1+n)%n, (x-1+n)%n, -1); add(x, x, n); upd(x); } void init(int _k, vector<int> _r) { k = _k, R = _r, n = R.size(); for(int i=0; i<2*base; ++i) { tree_max[i] = mp(-1, -1); } for(int i=0; i<n; ++i) { tree[i+base] = R[i]; } for(int i=base-1; i>=1; --i) { tree[i] = min(tree[i*2], tree[i*2+1]); } while(nr < n) { int cur = find_closest_zero(0, n-1); assert(cur != -1); solve(cur); } } bool is_bigger(int _x, int y) { int x = _x; while(x!=-1 && clw_dist(x, y)>=k) { x = ptr[x]; } if(x!=-1 && when[x] >= when[y]) return true; x = _x; while(x != -1 && clw_dist(y, x)>=k) { x = ptrr[x]; } if(x!=-1 && when[x] >= when[y]) return true; return false; } int compare_plants(int x, int y) { if(is_bigger(x, y)) return -1; if(is_bigger(y, x)) return 1; 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...