#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 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)
{
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])
{
tree[node] = tree[node * 2];
} else
{
tree[node] = tree[node * 2 + 1];
}
}
int minIndOn(int from, int to, int a, int b, int node)
{
if(tree[node] != 0) return -1;
if (a == b)
{
return a;
}
push(node);
int mid = (a + b) / 2;
int res = -1;
if (from <= mid) res = minIndOn(from, to, a, mid, node * 2);
if (res == -1 && to > mid) 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 (k == 2) return;
for (int i = 0; i < n; i++)
{
add(r[i], i, i, 0, n - 1, 1);
}
for (int t = 0; t < n; t++)
{
int res = -1;
int res1 = minIndOn(0, n - 1, 0, n - 1, 1);
if (res1 + k <= n - 1)
{
int res2 = minIndOn(res1 + k, n - 1, 0, n - 1, 1);
if (res2 != -1) res = res2;
else res = res1;
} else res = res1;
order[res] = t;
add(M, res, res, 0, n - 1, 1);
if (res != 0) add(-1, max(0, res - k + 1), res - 1, 0, n - 1, 1);
int still = k - (res - max(0, res - k + 1) + 1);
if (still > 0)
{
add(-1, n - still, n - 1, 0, n - 1, 1);
}
}
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 3 1
0 1 1 0 2
0 1
*/
