#include "plants.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "grader.cpp"
#endif // LOCAL
#define f first
#define s second
using namespace std;
const int N = 2e5 + 10, inf = 1e9 + 10;
int was[N], w[4 * N], n1;
pair<int, int> t[4 * N];
vector<int> a, p;
void push(int u){
t[2 * u + 1].f += w[u];
t[2 * u + 2].f += w[u];
w[2 * u + 1] += w[u];
w[2 * u + 2] += w[u];
w[u] = 0;
}
pair<int, int> cmp(pair<int, int> a, pair<int, int> b){
if(a.f > b.f)
return a;
else if(a.f < b.f)
return b;
else if(a.s < b.s)
return a;
else
return b;
}
void upd(int u, int tl, int tr, int l, int r, int val){
if(l <= tl && tr <= r){
t[u].f += val;
w[u] += val;
if(tl == tr)
t[u].s = tl;
return;
}
push(u);
int tm = (tl + tr) / 2;
if(l <= tm)
upd(2 * u + 1, tl, tm, l, r, val);
if(r >= tm + 1)
upd(2 * u + 2, tm + 1, tr, l, r, val);
t[u] = cmp(t[2 * u + 1], t[2 * u + 2]);
}
pair<int, int> get(int u, int tl, int tr, int l, int r){
// cout << u << " " << tl << " " << tr << " " << endl;
if(l <= tl && tr <= r)
return t[u];
push(u);
int tm = (tl + tr) / 2;
pair<int, int> res = {-inf, 0};
if(l <= tm)
res = cmp(res, get(2 * u + 1, tl, tm, l, r));
if(r >= tm + 1)
res = cmp(res, get(2 * u + 2, tm + 1, tr, l, r));
return res;
}
pair<int, int> get_lr(int l, int r){
if(l <= r)
return get(0, 0, n1 - 1, l, r);
else
return cmp(get(0, 0, n1 - 1, 0, r), get(0, 0, n1 - 1, l, n1 - 1));
}
void upd_lr(int l, int r){
if(l <= r)
upd(0, 0, n1 - 1, l, r, 1);
else{
upd(0, 0, n1 - 1, 0, r, 1);
upd(0, 0, n1 - 1, l, n1 - 1, 1);
}
}
void init(int K, vector<int> r) {
int k;
k = K;
a = r;
n1 = a.size();
p.resize(n1);
for(int j = 0; j < n1; ++j){
a[j] = k - 1 - a[j];
upd(0, 0, n1 - 1, j, j, a[j]);
}
for(int i = n1 - 1; i >= 0; --i){
// cout << i << endl;
int pos = get_lr(0, n1 - 1).s;
// cout << pos << endl;
// cout << i << endl;
pair<int, int> nxt = get_lr((pos + k) % n1, (pos - 1 + n1) % n1);
if(nxt.f == k - 1)
pos = nxt.s;
p[pos] = i;
upd(0, 0, n1 - 1, pos, pos, -inf);
upd_lr((pos - k + 1 + n1) % n1, pos);
// for(int i = 0; i < n; ++i)
// cout << p[i] << " ";
// cout << endl;
}
}
int compare_plants(int x, int y) {
if(p[x] > p[y])
return 1;
else
return -1;
}
/*
4 3 2
0 1 1 2
0 2
1 2
1
-1
5 3 3
2 2 0 0 0
0 2
1 2
2 4
*/
