Submission #1192931

#TimeUsernameProblemLanguageResultExecution timeMemory
1192931ildar1Comparing Plants (IOI20_plants)C++20
0 / 100
4078 ms296000 KiB
#include <iostream> #include <vector> #include <cassert> #include <stack> #define MAXN 200001 using namespace std; int ans[MAXN]; //ans[x] = rank of h[x] int myr[MAXN]; int next_bigger[MAXN]; //next_bigger[x] = index between x+1 and x+k-1 so that h[bigger[x]] int prev_bigger[MAXN]; //prev_bigger[x] = index between x-k+1 and x-1 so that h[prev_bigger[x]] is smallest term bigger than it else -1 stack<int> s; int n; int h; bool comparePairs(const pair<int,int> &p1, const pair<int,int> &p2) { if (p1.first < p2.first) return true; if (p1.first > p2.first) return false; if (p1.first==p2.first) { return p1.second >= p2.second; } } struct Seg{ pair<int,int> tree[2*MAXN]; int lazy[MAXN]; void make() { for (int i=0; i<n; i++) { tree[i+n].first = myr[i]; tree[i+n].second = i; } for (int i=n-1; i>0; i--) { tree[i] = min(tree[i<<1], tree[i<<1|1], comparePairs); /* tree[i] = min(tree[i<<1], tree[i<<1|1]); if (tree[i<<1].first==tree[i<<1|1].first) { tree[i].second = max(tree[i<<1|1].second, tree[i<<1].second); } */ } } void apply(int p, int val) { tree[p].first += val; if (p<n) lazy[p] += val; } void build(int p) { while (p>1) { p>>=1; tree[p] = min(tree[p<<1], tree[p<<1|1], comparePairs); /* int x = tree[p<<1].first; int y = tree[p<<1|1].first; if (x<=y) { tree[p].first = x + lazy[p]; tree[p].second = (x<y) ? tree[p<<1].second: max(tree[p<<1|1].second, tree[p<<1].second); } else { tree[p].first = y+ lazy[p]; tree[p].second = tree[p<<1|1].second; } */ } } void push(int p) { for (int i=h; i>0; i--) { int j = p>>i; if (lazy[j] != 0) { apply(j<<1, lazy[j]); apply(j<<1|1, lazy[j]); lazy[j] = 0; } } } void increm(int l, int r, int val) { l+=n; r+=n; int l0 = l; int r0 = r; for (; l<r; l>>=1, r>>=1) { if (l&1) apply(l++, val); if (r&1) apply(--r, val); } build(l0); build(r0-1); } pair<int, int> query(int l, int r) { l+=n; r+=n; push(l); push(r-1); pair<int,int> res = {2e9, -1}; for (; l<r; l>>=1, r>>=1) { if (l&1) res = min(res, tree[l++]); if (r&1) res = min(res, tree[--r]); /* if (l&1) { int tmp3 = res.first; int tmp2 = res.second; res = min(res, tree[l]); if (tmp3==tree[l].first) res.second = max(tmp2, tree[l].second); l++; } if (r&1) { int tmp3 = res.first; int tmp2 = res.second; r--; res = min(res, tree[r]); if (tmp3==tree[r].first) res.second = max(tmp2, tree[r].second); } */ } return res; } } seg; void init(int k, vector<int> r) { n = r.size(); h = 31 - __builtin_clz(n); for (int i=0; i<n; i++) myr[i] = r[i]; seg.make(); int ind=seg.query(0,n).second; s.push(ind); for (int m=0; m<n; m++) { while (true) { if (!s.empty()) { int tmp = s.top(); if (tmp>=k-1 && seg.query(tmp-k+1, tmp).first>0) { s.pop(); ind = tmp; break; } else if (tmp>= k-1) { s.push(seg.query(tmp-k+1,tmp).second); } else if (tmp<k-1 && seg.query(0, tmp).first>0 && seg.query(n-k+tmp+1,n).first>0) { s.pop(); ind = tmp; break; } else if (tmp<k-1 && seg.query(0,tmp).first>0) { s.push(seg.query(n-k+tmp+1,n).second); } else { s.push(seg.query(0,tmp).second); } } else { if (seg.query(0, ind).first==0) { s.push(seg.query(0, ind).second); } else { s.push(seg.query(0, n).second); } } } ans[ind] = n-m; if (ind >= k-1) { seg.increm(ind-k+1, ind, -1); } else { seg.increm(0, ind, -1); seg.increm(n-k+ind+1, n, -1); } seg.increm(ind, ind+1, n); } } int compare_plants(int x, int y) { if (ans[x] > ans[y]) { return 1; } else return -1; }

Compilation message (stderr)

plants.cpp: In function 'bool comparePairs(const std::pair<int, int>&, const std::pair<int, int>&)':
plants.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
   28 | }
      | ^
#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...