#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>k0, k1;
int K, n;
vector<int>A;
struct ST
{
int l, r;
pair<int, int> mn;
pair<int, int> mn1;
int del = 0;
int del1 = 0;
ST *left, *right;
ST(int l, int r, vector<int>&a): l(l), r(r)
{
if (l < r)
{
left = new ST(l, (l + r) / 2, a);
right = new ST((l + r) / 2 + 1, r, a);
mn = min(left->mn, right->mn);
}
else
mn = {a[l], l};
mn1 = mn;
}
void fix()
{
if (l == r)
{
mn.first += del;
del = 0;
}
else
{
mn.first += del;
left->del += del;
right->del += del;
del = 0;
}
}
void fix1()
{
if (l == r)
{
mn1.first += del1;
del1 = 0;
}
else
{
mn1.first += del1;
left->del1 += del1;
right->del1 += del1;
del1 = 0;
}
}
void add(int x, int y, int w)
{
if (x <= l && r <= y)
{
del += w;
return fix();
}
fix();
if (r < x || y < l)
return;
left->add(x, y, w);
right->add(x, y, w);
mn = min(left->mn, right->mn);
}
void add1(int x, int y, int w)
{
if (x <= l && r <= y)
{
del1 += w;
return fix1();
}
fix1();
if (r < x || y < l)
return;
left->add1(x, y, w);
right->add1(x, y, w);
mn1 = min(left->mn1, right->mn1);
}
};
bitset<1000>B[200000];
void init(int k, vector<int> r)
{
K = k;
n = r.size();
if (k == 2)
{
k0 = k1 = vector<int>(n, 0);
for (int t = 0; t < 2; t++)
for (int i = n - 1; i >= 0; i--)
{
if (r[i] == 0)
k0[i] = 1 + k0[(i + 1) % n];
else
k1[i] = 1 + k1[(i + 1) % n];
}
return;
}
if (2 * k > n)
{
ST medis(0, n - 1, r);
auto add = [&](int x, int y, int w)
{
while (y >= n)
{
x -= n;
y -= n;
}
while (x < 0)
{
x += n;
y += n;
}
if (y < n)
{
medis.add(x, y, w);
}
else
{
medis.add(x, n - 1, w);
medis.add(0, y - n, w);
}
};
auto add1 = [&](int x, int y, int w)
{
while (y >= n)
{
x -= n;
y -= n;
}
while (x < 0)
{
x += n;
y += n;
}
if (y < n)
{
medis.add1(x, y, w);
}
else
{
medis.add1(x, n - 1, w);
medis.add1(0, y - n, w);
}
};
while (medis.mn1.first == 0)
{
int i = medis.mn1.second;
add(i + 1, i + (k - 1), 1);
add1(i, i, 1);
}
A = vector<int>(n, -1);
for (int tt = 0; tt < n; tt++)
{
while (medis.mn1.first == 0)
{
int i = medis.mn1.second;
add(i + 1, i + (k - 1), 1);
add1(i, i, 1);
}
int i = medis.mn.second;
add(i + 1, i + (k - 1), -1);
add(i - (k - 1), i - 1, -1);
add1(i - (k - 1), i - 1, -1);
A[i] = tt;
add(i, i, n + 10000);
add1(i, i, n + 10000);
r[i] = n + 100;
}
return;
}
ST medis(0, n - 1, r);
auto add = [&](int x, int y, int w)
{
while (y >= n)
{
x -= n;
y -= n;
}
while (x < 0)
{
x += n;
y += n;
}
if (y < n)
{
medis.add(x, y, w);
}
else
{
medis.add(x, n - 1, w);
medis.add(0, y - n, w);
}
};
auto add1 = [&](int x, int y, int w)
{
while (y >= n)
{
x -= n;
y -= n;
}
while (x < 0)
{
x += n;
y += n;
}
if (y < n)
{
medis.add1(x, y, w);
}
else
{
medis.add1(x, n - 1, w);
medis.add1(0, y - n, w);
}
};
while (medis.mn1.first == 0)
{
int i = medis.mn1.second;
add(i + 1, i + (k - 1), 1);
add1(i, i, 1);
}
vector<int>K;
for (int tt = 0; tt < n; tt++)
{
while (medis.mn1.first == 0)
{
int i = medis.mn1.second;
add(i + 1, i + (k - 1), 1);
add1(i, i, 1);
}
int i = medis.mn.second;
add(i + 1, i + (k - 1), -1);
add(i - (k - 1), i - 1, -1);
add1(i - (k - 1), i - 1, -1);
add(i, i, n + 10000);
add1(i, i, n + 10000);
K.push_back(i);
r[i] = n + 100;
}
reverse(K.begin(), K.end());
vector<int>ok;
for (int i : K)
{
for (int j : ok)
{
int d = min({abs(j - i), abs(j - i + n), abs(j - i - n)});
if (d <= k - 1)
{
B[i][j] = 1;
B[i] |= B[j];
}
}
ok.push_back(i);
}
}
int compare_plants(int x, int y)
{
assert(x < y);
if (K == 2)
{
if (k0[x] >= y - x)
return 1;
if (k1[x] >= y - x)
return -1;
if (k0[y] >= n - y + x)
return -1;
if (k1[y] >= n - y + x)
return 1;
return 0;
}
if (!A.empty())
{
if (A[x] < A[y])
return 1;
else
return -1;
}
if (B[x][y])
return 1;
if (B[y][x])
return -1;
return 0;
}
