#include <bits/stdc++.h>
#include "plants.h"
#define ll long long
#define inf (ll)1e17
#define dbg(x) cerr << #x << ' ' << x << endl;
using namespace std;
vector<ll> p;
ll n;
// ----- sizes & buffers (arrays instead of vectors) -----
static const int MAXN = 200000; // must cover max n
static const int SZ = 4 * MAXN + 5;
ll tree[SZ]; // was vector<ll> tree
ll lazy[SZ]; // was vector<ll> lazy
ll chajara[SZ]; // was vector<ll> chajara
ll kassoul[SZ]; // was vector<ll> kassoul
// (Global arrays have zero-initialization by default.)
void printvec(vector<ll>& vec)
{
for (auto &&e : vec) cout << e << ' ';
cout << endl;
}
// ----- segment tree helpers now take raw pointers -----
void prop(ll node, ll l, ll r, ll* tre, ll* laz)
{
tre[node] += laz[node];
if (l == r) {
laz[node] = 0;
return;
}
laz[node * 2 + 1] += laz[node];
laz[node * 2 + 2] += laz[node];
laz[node] = 0;
}
void update(ll node, ll l, ll r, ll x, ll y, ll val, ll* tre, ll* laz)
{
prop(node, l, r, tre, laz);
if (max(l, x) > min(r, y)) return;
if (x <= l && r <= y) {
laz[node] += val;
prop(node, l, r, tre, laz);
return;
}
ll mid = (l + r) / 2;
update(node * 2 + 1, l, mid, x, y, val, tre, laz);
update(node * 2 + 2, mid + 1, r, x, y, val, tre, laz);
tre[node] = min(tre[node * 2 + 1], tre[node * 2 + 2]);
}
ll query(ll node, ll l, ll r, ll x, ll y, ll* tre, ll* laz)
{
prop(node, l, r, tre, laz);
if (max(l, x) > min(r, y)) return inf;
if (x <= l && r <= y) return tre[node];
ll mid = (l + r) >> 1;
return min(
query(node * 2 + 1, l, mid, x, y, tre, laz),
query(node * 2 + 2, mid + 1, r, x, y, tre, laz)
);
}
void decrease(ll l, ll r)
{
if (l <= r) {
update(0, 0, n - 1, l, r, -1, tree, lazy);
} else {
update(0, 0, n - 1, l, n - 1, -1, tree, lazy);
if (r >= 0) update(0, 0, n - 1, 0, r, -1, tree, lazy);
}
}
ll findsmallest(ll l, ll r, ll* tre, ll* laz)
{
ll ans = r + 1;
ll oldl = l;
while (l <= r) {
ll mid = (l + r) >> 1;
ll vl = query(0, 0, n - 1, oldl, mid, tre, laz);
if (vl == 0) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
void init(int k, std::vector<int> r)
{
n = (ll)r.size();
// safety check for array bounds
if (n > MAXN) {
// handle as you prefer (assert/exit); using assert here:
assert(false && "n exceeds MAXN");
}
p.resize(n);
vector<bool> vis(n, false);
for (int i = 0; i < n; i++) r[i] = k - 1 - r[i];
for (int i = 0; i < n; i++) {
if (r[i] == 0) {
if (i + k <= n) {
update(0, 0, n - 1, i + 1, i + k - 1, 1, chajara, kassoul);
} else {
if (i < n - 1) update(0, 0, n - 1, i + 1, n - 1, 1, chajara, kassoul);
update(0, 0, n - 1, 0, (i + k - 1) % n, 1, chajara, kassoul);
}
}
}
for (int i = 0; i < n; i++) {
update(0, 0, n - 1, i, i, r[i], tree, lazy);
}
for (int i = 0; i < n; i++) {
ll ind = findsmallest(0, n - 1, tree, lazy);
ll index = ind + k;
if (ind < n - 1) index = findsmallest(ind + 1, n - 1, chajara, kassoul);
if (index < n) {
ll vl = findsmallest(index, n - 1, tree, lazy);
if (vl != n) ind = vl;
}
vis[ind] = true;
update(0, 0, n - 1, ind, ind, inf, tree, lazy);
p[ind] = i;
decrease((ind - k + 1 + n) % n, ind - 1);
if (ind + k <= n) {
update(0, 0, n - 1, ind + 1, ind + k - 1, -1, chajara, kassoul);
} else {
if (ind < n - 1) update(0, 0, n - 1, ind + 1, n - 1, -1, chajara, kassoul);
update(0, 0, n - 1, 0, (ind + k - 1) % n, -1, chajara, kassoul);
}
ll j = max(0LL, ind - (ll)k + 1);
while (j <= ind - 1) {
j = findsmallest(j, ind - 1, tree, lazy);
if (j == ind) break;
if (j + k <= n) {
update(0, 0, n - 1, j + 1, j + k - 1, 1, chajara, kassoul);
} else {
if (j < n - 1) update(0, 0, n - 1, j + 1, n - 1, 1, chajara, kassoul);
update(0, 0, n - 1, 0, (j + k - 1) % n, 1, chajara, kassoul);
}
j++;
}
if (ind - (ll)k + 1 < 0) {
j = ind - (ll)k + 1 + n;
while (j < n) {
j = findsmallest(j, n - 1, tree, lazy);
if (j == n) break;
if (j + k <= n) {
update(0, 0, n - 1, j + 1, j + k - 1, 1, chajara, kassoul);
} else {
if (j < n - 1) update(0, 0, n - 1, j + 1, n - 1, 1, chajara, kassoul);
update(0, 0, n - 1, 0, (j + k - 1) % n, 1, chajara, kassoul);
}
j++;
}
}
}
}
int compare_plants(int x, int y)
{
if (p[x] < p[y]) return -1;
return 1;
}
