#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) {
return true;
}
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]);
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;
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) {
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();
//find the first zero;
/* pair<int, int> first = seg.query(0, n);
int ind = first.second;
if (ind<k-1) {
pair<int, int> sec = seg.query(n-k+ind+1, n);
if (sec.first==0) {
while (true) {
pair<int, int> ano = seg.query(ind+1, n);
if (ano.second - ind>k-1) {
ind = ano.second;
break;
}
ind = ano.second;
}
}
} */
int ind=seg.query(0,n).second;
s.push(ind);
for (int m=0; m<n; m++) {
/* pair<int, int> first = seg.query(0, n);
int ind = first.second;
if (ind<k-1) {
pair<int, int> sec = seg.query(n-k+ind+1, n);
if (sec.first==0) {
ind = sec.second;
}
} */
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |