#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
int k;
vector<int> r;
vector<int> prefR;
const int N = 200005;
int tree[4 * N];
int treeInd[4 * N];
int lazy[4 * N];
const int M = 1000000000;
int n;
int getSum(int from, int to)
{
int res = prefR[to + 1];
res -= prefR[from];
return res;
}
void push(int node)
{
for (int i = 0; i <= 1; i++)
{
tree[node * 2 +i] += lazy[node];
lazy[node * 2 + i] += lazy[node];
}
lazy[node] = 0;
}
void add(int num, int from, int to, int a, int b, int node)
{
if (from <= a && b <= to)
{
if (a == b) treeInd[node] = a;
tree[node] += num;
lazy[node] += num;
return;
}
push(node);
int mid = (a + b) / 2;
if (from <= mid) add(num, from, to, a, mid, node * 2);
if (to > mid) add(num, from, to, mid + 1, b, node * 2+ 1);
if (tree[node * 2] <= tree[node * 2 +1])
{
treeInd[node] = treeInd[node * 2];
tree[node] = tree[node * 2];
} else
{
treeInd[node] = treeInd[node * 2 + 1];
tree[node] = tree[node * 2 + 1];
}
}
array<int, 2> minIndOn(int from, int to, int a, int b, int node)
{
if (from <= a && b <= to)
{
return {tree[node], treeInd[node]};
}
push(node);
int mid = (a + b) / 2;
array<int, 2> res = {M, -1};
if (from <= mid) res = min(res, minIndOn(from, to, a, mid, node *2));
if (to > mid) res = min(res, minIndOn(from, to, mid + 1, b, node * 2 + 1));
return res;
}
vector<int> order;
void init(int K, std::vector<int> R) {
k = K;
r = R;
n = r.size();
prefR.resize(r.size() + 1);
for (int i = 1; i <= r.size(); i++)
{
prefR[i] = r[i - 1];
prefR[i] += prefR[i - 1];
}
order.resize(n);
if (2 * k > n)
{
/*
for (int i = 0; i < n; i++)
{
add(r[i], i, i, 0, n - 1, 1);
} */
for (int t = 0; t < n; t++)
{
array<int, 2> res = {-1, -1};
array<int,2> res1 = {M, -1};
for (int i = 0; i < n; i++)
{
res1 = min(res1, {r[i], i});
}
if (res1[1] + k <= n - 1)
{
array<int, 2> res2 = {M, -1};
for (int i = res1[1] + k; i < n; i++)
{
res2 = min(res2, {r[i], i});
}
if (res2[0] == 0) res = res2;
else res = res1;
} else res = res1;
order[res[1]] = t;
//add(M, res[1], res[1], 0, n - 1, 1);
r[res[1]] += M;
for (int i = max(0, res[1] - k + 1); i < res[1]; i++) r[i]--;
//if (res[1] != 0) add(-1, max(0, res[1] - k + 1), res[1] - 1, 0, n - 1, 1);
int still = k - (res[1] - max(0, res[1] - k + 1) + 1);
for (int i = n - still; i < n; i++) r[i]--;
if (still > 0)
{
//add(-1, n - still, n - 1, 0, n - 1, 1);
}
//for (int i : r) cout << i << " ";
//cout << endl;
}
}
return;
}
int compare_plants(int x, int y) {
if (k == 2)
{
if (getSum(x, y - 1) == (y - x)) return -1;
if (getSum(x, y - 1) == 0) return 1;
int sum1 = getSum(y, n -1);
if (x != 0) sum1 += getSum(0, x - 1);
if (sum1 == (n - y) + x) return 1;
if (sum1 == 0) return -1;
return 0;
}
if (order[x] < order[y])
{
return 1;
}
if (order[x] > order[y]) return -1;
return 0;
}
//3 2 1 4 0
/*
5 5 1
0 1 1 0 2
0 1
*/
