#include "plants.h"
#include <iostream>
#include <vector>
#include <map>
#define ll long long
using namespace std;
ll n, k, nx[200000], A[200000];
vector <ll> adj[200000];
map <ll, ll> mp, mp2, mp3, mp4;
vector <ll> V, U;
struct SegTree{
ll st[800000], lazy[800000];
void build(ll id, ll l, ll r) {
lazy[id] = 0;
if (l == r) {
st[id] = A[l];
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = min(st[id*2], st[id*2+1]);
}
void push_down(ll id) {
st[id*2] -= lazy[id];
st[id*2+1] -= lazy[id];
lazy[id*2] += lazy[id];
lazy[id*2+1] += lazy[id];
lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
++lazy[id];
--st[id];
query(id, l, r);
return;
}
push_down(id);
ll mid = (l+r)/2;
update(id*2, l, mid, ql, qr);
update(id*2+1, mid+1, r, ql, qr);
st[id] = min(st[id*2], st[id*2+1]);
}
void query(ll id, ll l, ll r) {
if (st[id] > 0) return;
if (l == r) {
st[id] = 1e18;
U.push_back(l);
return;
}
push_down(id);
ll mid = (l+r)/2;
query(id*2, l, mid);
query(id*2+1, mid+1, r);
st[id] = min(st[id*2], st[id*2+1]);
}
}ST;
bool dist(ll a, ll b) {
if (a < b) return (b-a < k ? 1 : 0);
else return (b-a+n < k ? 1 : 0);
}
void fix(ll x) {
auto it = mp.lower_bound(x);
if (it != mp.end() && dist(x, it->first)) {
nx[x] = it->first;
mp.erase(it);
return;
}
it = mp.begin();
if (it != mp.end() && dist(x, it->first)) {
nx[x] = it->first;
mp.erase(it);
return;
}
}
void check(ll x) {
auto it = mp2.lower_bound(x);
if (it != mp2.begin()) {
it = prev(it);
if (dist(it->first, x)) {
mp.erase(x);
nx[it->first] = x;
return;
}
}
else if (mp2.size() != 1) {
it = prev(mp2.end());
if (dist(it->first, x)) {
mp.erase(x);
nx[it->first] = x;
return;
}
}
}
void add_edge(ll x) {
auto it = mp3.lower_bound(x);
while (it != mp3.end() && dist(x, it->first)) {
auto nx = next(it);
//cout << it->first << " " << x << endl;
adj[it->first].push_back(x);
mp3.erase(it);
it = nx;
}
it = mp3.begin();
while (it != mp3.end() && dist(x, it->first)) {
auto nx = next(it);
//cout << it->first << " " << x << endl;
adj[it->first].push_back(x);
mp3.erase(it);
it = nx;
}
it = mp4.lower_bound(x);
if (it != mp4.begin()) {
it = prev(it);
while (x != it->first) {
if (!dist(it->first, x)) break;
//cout << it->first << "*" << x << endl;
adj[it->first].push_back(x);
if (it == mp4.begin()) {
mp4.erase(it);
break;
}
auto pv = prev(it);
mp4.erase(it);
it = pv;
}
}
it = mp4.end();
if (it != mp4.begin()) {
it = prev(it);
while (x != it->first) {
if (!dist(it->first, x)) break;
adj[it->first].push_back(x);
//cout << it->first << "*" << x << endl;
if (it == mp4.begin()) {
mp4.erase(it);
break;
}
auto pv = prev(it);
mp4.erase(it);
it = pv;
}
}
++mp3[x], ++mp4[x];
}
void init(int _k, std::vector<int> r) {
n = r.size(), k = _k;
mp.clear();
mp2.clear();
mp3.clear();
mp4.clear();
for (int i=0; i<n; ++i) nx[i] = -1, A[i] = r[i], adj[i].clear();
for (int i=0; i<n; ++i) {
if (A[i] == 0) V.push_back(i), ++mp[i], ++mp2[i], A[i] = 1e18;
}
ST.build(1, 0, n-1);
for (int i=0; i+1<V.size(); ++i) {
if (dist(V[i], V[i+1])) {
mp.erase(V[i+1]);
nx[V[i]] = V[i+1];
}
}
if (V.size() != 1 && dist(V.back(), V[0])) {
mp.erase(V[0]);
nx[V.back()] = V[0];
}
while (!mp.empty()) {
auto it = mp.begin();
ll u = it->first;
add_edge(u);
mp.erase(it);
mp2.erase(u);
ll l = (u-k+1+n)%n, r = (u-1+n)%n;
U.clear();
if (l <= r) ST.update(1, 0, n-1, l, r);
else {
ST.update(1, 0, n-1, l, n-1);
ST.update(1, 0, n-1, 0, r);
}
if (!U.empty()) {
for (int i=0; i+1<U.size(); ++i) {
++mp2[U[i]];
nx[U[i]] = U[i+1];
}
++mp2[U.back()];
fix(U[0]);
++mp[U[0]];
check(U[0]);
}
if (nx[u] != -1) {
fix(nx[u]);
++mp[nx[u]], ++mp2[nx[u]];
check(nx[u]);
}
}
return;
}
bool visited[200000];
void dfs(ll u) {
if (visited[u]) return;
visited[u] = 1;
for (auto v : adj[u]) {
if (!visited[v]) dfs(v);
}
}
bool query(ll x, ll y) {
for (int i=0; i<n; ++i) visited[i] = 0;
dfs(x);
if (visited[y]) return 1;
else return 0;
}
int compare_plants(int x, int y) {
if (query(x, y)) return 1;
else if (query(y, x)) return -1;
else return 0;
}
