#include "plants.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
using namespace std;
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
const int INF = 1e9 + 7;
ll n, k;
vector<int>a;
vector<int>cons0, cons1;
bool ent1 = false;
pair<int, int> t[800007];
int lazy[1600007];
vector<int>vals;
void push(int v) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
t[v].ff += lazy[v];
lazy[v] = 0;
}
void build(int v, int tl, int tr) {
if (tl == tr) {
t[v] = { a[tl],tl };
}
else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
t[v] = min(t[2 * v], t[2 * v + 1]);
}
}
pair<int, int> get_min(int v, int tl, int tr, int l, int r) {
push(v);
if (l > r)return { INF,INF };
if (tl >= l && tr <= r)return t[v];
else {
int tm = (tl + tr) / 2;
return min(get_min(2 * v, tl, tm, l, min(r, tm)),
get_min(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
}
void update(int v, int tl, int tr, int ind, int val) {
push(v);
if (tl == tr) {
t[v].ff = val;
//cout << "Updating: ";
//cout << t[v].ff << " " << t[v].ss << endl;
}
else {
int tm = (tl + tr) / 2;
if (ind <= tm) {
update(2 * v, tl, tm, ind, val);
}
else update(2 * v + 1, tm + 1, tr, ind, val);
t[v] = min(t[2 * v], t[2 * v + 1]);
}
}
void add_r(int v, int tl, int tr, int l, int r, int val) {
push(v);
if (l > r)return;
if (tl >= l && tr <= r) {
lazy[v] += val;
push(v);
}
else {
int tm = (tl + tr) / 2;
add_r(2 * v, tl, tm, l, min(r, tm), val);
add_r(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
t[v] = min(t[2 * v], t[2 * v + 1]);
}
}
int her(int x, int y) {
if (y < x)y += n;
return y - x;
}
void init(int K, vector<int> r) {
n = r.size();
k = K;
a = r;
if (k == 2) {
ent1 = true;
int cur0 = 0, cur1 = 0;
int f1 = 0, f0 = 0;
cons0.resize(n, 0);
cons1.resize(n, 0);
for (int i = 0; i < 2 * n; i++) {
if (r[i % n] == 1) {
if (cur0 != 0) {
while (f0 != i % n) {
cons0[f0] = cur0;
f0++;
cur0--;
f0 %= n;
}
f1 = i % n;
}
cur1++;
}
else {
if (cur1 != 0) {
while (f1 != i % n) {
cons1[f1] = cur1;
f1++;
cur1--;
f1 %= n;
}
f0 = i % n;
}
cur0++;
}
}
/*for (auto x : cons0) {
cout << x << " ";
}
cout << endl;
for (auto x : cons1) {
cout << x << " ";
}
cout << endl;*/
}
else {
build(1, 0, n - 1);
vals.resize(n, 0);
int curval = n;
for (int i = 0; i < n; i++) {
pair<int, int>mn, mn2;
pair<int, int>mn1 = get_min(1, 0, n - 1, 0, n - 1);
int vl = mn1.ss - k + 1;
if (vl < 0) {
mn2 = min(get_min(1, 0, n - 1, 0, mn1.ss - 1),
get_min(1, 0, n - 1, vl + n, n - 1));
}
else {
mn2 = get_min(1, 0, n - 1, vl, mn1.ss - 1);
}
if (mn1.ff == mn2.ff) {
mn1 = mn2;
vl = mn1.ss - k + 1;
if (vl < 0) {
mn2 = min(get_min(1, 0, n - 1, 0, mn1.ss - 1),
get_min(1, 0, n - 1, vl + n, n - 1));
}
else {
mn2 = get_min(1, 0, n - 1, vl, mn1.ss - 1);
}
if (mn1.ff == mn2.ff) {
mn1 = mn2;
vl = mn1.ss - k + 1;
if (vl < 0) {
mn2 = min(get_min(1, 0, n - 1, 0, mn1.ss - 1),
get_min(1, 0, n - 1, vl + n, n - 1));
}
else {
mn2 = get_min(1, 0, n - 1, vl, mn1.ss - 1);
}
if (mn1.ff == mn2.ff) {
mn1 = mn2;
vl = mn1.ss - k + 1;
if (vl < 0) {
mn2 = min(get_min(1, 0, n - 1, 0, mn1.ss - 1),
get_min(1, 0, n - 1, vl + n, n - 1));
}
else {
mn2 = get_min(1, 0, n - 1, vl, mn1.ss - 1);
}
if (mn1.ff == mn2.ff) {
mn = mn2;
}
else {
mn = mn1;
}
}
else {
mn = mn1;
}
}
else {
mn = mn1;
}
}
else {
mn = mn1;
}
update(1, 0, n - 1, mn.ss, INF);
/*cout << "Min: ";
cout << mn.ff << " " << mn.ss << endl;*/
vl = mn.ss - k + 1;
if (vl < 0) {
add_r(1, 0, n - 1, 0, mn.ss, -1);
add_r(1, 0, n - 1, vl + n, n - 1, -1);
}
else {
add_r(1, 0, n - 1, vl, mn.ss, -1);
}
vals[mn.ss] = curval--;
/*for (int i = 0; i < n; i++) {
cout << get_min(1, 0, n - 1, i, i).ff << " " <<
get_min(1, 0, n - 1, i, i).ss << " ";
}
cout << endl;*/
}
}
}
int compare_plants(int x, int y) {
if (ent1) {
if (cons0[x] >= her(x, y) || cons1[y] >= her(y, x)) {
return 1;
}
if (cons1[x] >= her(x, y) || cons0[y] >= her(y, x)) {
return -1;
}
return 0;
}
else {
if (vals[x] > vals[y])return 1;
else return -1;
}
}
/*
4 2 3
1 1 0 0
0 1
0 2
0 3
4 3 6 0 1 1 2 0 1 0 2 0 3 1 2 1 3 2 3
1 1 1 -1 1 1
7 4 7 0 2 1 2 1 3 0 0 2 0 4 0 6 5 3 4 6 6 4 6 5
1 -1 -1 -1 -1 1 1
*/
