#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
class PotentialMaximum {
public:
PotentialMaximum() {}
PotentialMaximum(int n, int k, vector<int> r) : n(n), k(k), tree(2 * n) {
Build(1, 0, n - 1, r);
}
void UpdateIndeg(int x, int z = 1) {
int l = x + 1;
int r = x + k - 1;
while (l >= n) {
l -= n;
r -= n;
}
if (n <= r) {
Update(1, 0, n - 1, l, n - 1, 0, z);
Update(1, 0, n - 1, 0, r - n, 0, z);
} else {
Update(1, 0, n - 1, l, r, 0, z);
}
}
void UpdateRank(int x, int z) {
int l = x - k + 1;
int r = x - 1;
while (l < 0) {
l += n, r += n;
}
if (n <= r) {
Update(1, 0, n - 1, l, n - 1, z, 0);
Update(1, 0, n - 1, 0, r - n, z, 0);
} else {
Update(1, 0, n - 1, l, r, z, 0);
}
}
void Delete(int x) {
UpdateRank(x, -1);
UpdateIndeg(x, -1);
Update(1, 0, n - 1, x, x, 1e9, 1e9);
}
int Query() {
return tree[1].id;
}
private:
struct Node {
int id;
int rank;
int indeg;
int lazyrank;
int lazyindeg;
};
int n, k;
vector<Node> tree;
void Apply(int u, int r, int d) {
tree[u].rank += r;
tree[u].lazyrank += r;
tree[u].indeg += d;
tree[u].lazyindeg += d;
}
void Push(int u, int lc, int rc) {
Apply(lc, tree[u].lazyrank, tree[u].lazyindeg);
Apply(rc, tree[u].lazyrank, tree[u].lazyindeg);
tree[u].lazyrank = 0;
tree[u].lazyindeg = 0;
}
void Pull(int u, int lc, int rc) {
if (tree[lc].rank != tree[rc].rank) {
if (tree[lc].rank < tree[rc].rank) {
tree[u] = tree[lc];
} else {
tree[u] = tree[rc];
}
} else {
if (tree[lc].indeg < tree[rc].indeg) {
tree[u] = tree[lc];
} else {
tree[u] = tree[rc];
}
}
tree[u].lazyrank = 0;
tree[u].lazyindeg = 0;
}
void Build(int u, int tl, int tr, const vector<int> &r) {
if (tl == tr) {
tree[u].id = tl;
tree[u].rank = r[tl];
tree[u].indeg = 0;
tree[u].lazyrank = 0;
tree[u].lazyindeg = 0;
return;
}
int md = (tl + tr) / 2;
int lc = u + 1;
int rc = u + 2 * (md - tl + 1);
Build(lc, tl, md, r);
Build(rc, md + 1, tr, r);
Pull(u, lc, rc);
}
void Update(int u, int tl, int tr, int l, int r, int rank, int indeg) {
if (l > tr || tl > r || tl > tr || l > r) {
return;
}
if (l <= tl && tr <= r) {
return Apply(u, rank, indeg);
}
int md = (tl + tr) / 2;
int lc = u + 1;
int rc = u + 2 * (md - tl + 1);
Push(u, lc, rc);
Update(lc, tl, md, l, r, rank, indeg);
Update(rc, md + 1, tr, l, r, rank, indeg);
Pull(u, lc, rc);
}
};
class Relax {
public:
Relax() {}
Relax(int n, int k, vector<int> r) : n(n), k(k), tree(2 * n) {
Build(1, 0, n - 1, r);
}
void Update(int x) {
int l = x - k + 1;
int r = x - 1;
while (l < 0) {
l += n, r += n;
}
if (n <= r) {
Update(1, 0, n - 1, l, n - 1, -1);
Update(1, 0, n - 1, 0, r - n, -1);
} else {
Update(1, 0, n - 1, l, r, -1);
}
}
void Delete(int x) {
Update(1, 0, n - 1, x, x, 1e9);
}
pair<int, int> Query(int x) {
int l = x - k + 1;
int r = x - 1;
while (l < 0) {
l += n, r += n;
}
Node res;
if (n <= r) {
auto ll = Query(1, 0, n - 1, l, n - 1);
auto rr = Query(1, 0, n - 1, 0, r - n);
if (ll.rank < rr.rank) {
res = ll;
} else {
res = rr;
}
} else {
res = Query(1, 0, n - 1, l, r);
}
return {res.id, res.rank};
}
private:
struct Node {
int id;
int rank;
int lazyrank;
};
int n, k;
vector<Node> tree;
void Apply(int u, int r) {
tree[u].rank += r;
tree[u].lazyrank += r;
}
void Push(int u, int lc, int rc) {
Apply(lc, tree[u].lazyrank);
Apply(rc, tree[u].lazyrank);
tree[u].lazyrank = 0;
}
void Pull(int u, int lc, int rc) {
if (tree[lc].rank < tree[rc].rank) {
tree[u] = tree[lc];
} else {
tree[u] = tree[rc];
}
tree[u].lazyrank = 0;
}
void Build(int u, int tl, int tr, const vector<int> &r) {
if (tl == tr) {
tree[u].id = tl;
tree[u].rank = r[tl];
tree[u].lazyrank = 0;
return;
}
int md = (tl + tr) / 2;
int lc = u + 1;
int rc = u + 2 * (md - tl + 1);
Build(lc, tl, md, r);
Build(rc, md + 1, tr, r);
Pull(u, lc, rc);
}
void Update(int u, int tl, int tr, int l, int r, int rank) {
if (l > tr || tl > r || tl > tr || l > r) {
return;
}
if (l <= tl && tr <= r) {
return Apply(u, rank);
}
int md = (tl + tr) / 2;
int lc = u + 1;
int rc = u + 2 * (md - tl + 1);
Push(u, lc, rc);
Update(lc, tl, md, l, r, rank);
Update(rc, md + 1, tr, l, r, rank);
Pull(u, lc, rc);
}
Node Query(int u, int tl, int tr, int l, int r) {
if (l > tr || tl > r || tl > tr || l > r) {
return Node({-1, (int) 1e9, (int) 1e9});
}
if (l <= tl && tr <= r) {
return tree[u];
}
int md = (tl + tr) / 2;
int lc = u + 1;
int rc = u + 2 * (md - tl + 1);
Push(u, lc, rc);
auto ll = Query(lc, tl, md, l, r);
auto rr = Query(rc, md + 1, tr, l, r);
if (ll.rank < rr.rank) {
return ll;
} else {
return rr;
}
}
};
int n, k;
vector<int> h;
// Greedily find a valid arrangement h
// Indices i, j are comparable if |i - j| < k
// x and y are comparable if there exists a sequence
// h[x] < h[i1] < h[i2] < ... < h[y] and adjacent elements
// have distance < k.
void init(int k, vector<int> r) {
n = (int) r.size();
::k = k;
h.assign(n, -1);
Relax relax(n, k, r);
PotentialMaximum maxim(n, k, r);
for (int i = 0; i < n; i++) {
if (r[i] == 0) {
relax.Delete(i);
maxim.UpdateIndeg(i);
}
}
for (int v = n - 1; v >= 0; v--) {
int id = maxim.Query();
h[id] = v;
relax.Update(id);
maxim.Delete(id);
while (relax.Query(id).second == 0) {
int p = relax.Query(id).first;
maxim.UpdateIndeg(p);
relax.Delete(p);
}
}
}
int compare_plants(int x, int y) {
return h[x] > h[y] ? 1 : -1;
}
