#include "plants.h"
#include <vector>
#include <iostream>
using namespace std;
int N;
int K;
const long long INF = 1e9;
const int logN = 19;
vector<int> H;
int** left_high;
int** right_high;
int dist(int x, int y) //clockwise distance from x to y
{
while(x < 0) x += N;
while(y < 0) y += N;
x = x % N;
y = y % N;
if(y < x) y = y + N;
return y - x;
}
struct segtree
{
int l;
int r;
pair<long long, int> mn; //min first, index second
pair<long long, int> mx; //max first, index second
int lp = 0;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
mn = make_pair(0, l);
mx = make_pair(0, l);
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void add(int L, int R, long long V)
{
L = (L + 10*N) % N;
R = (R + 10*N) % N;
if(R < L)
{
add(L, N-1, V);
add(0, R, V);
return;
}
if(R < l || r < L) return;
else if(L <= l && r <= R)
{
lp += V;
mn.first += V;
mx.first += V;
}
else
{
left->add(L, R, V);
right->add(L, R, V);
mn = min(left->mn, right->mn);
mn.first += lp;
mx = max(left->mx, right->mx);
mx.first += lp;
}
}
pair<long long, int> rangemin(int L, int R)
{
L = (L + 10*N) % N;
R = (R + 10*N) % N;
if(R < L)
{
return min(rangemin(L, N-1), rangemin(0, R));
}
if(R < l || r < L) return make_pair(+2*INF, -1);
else if(L <= l && r <= R)
{
return mn;
}
else
{
pair<long long, int> A = min(left->rangemin(L, R), right->rangemin(L, R));
A.first += lp;
return A;
}
}
pair<long long, int> rangemax(int L, int R)
{
L = (L + 10*N) % N;
R = (R + 10*N) % N;
if(R < L)
{
return max(rangemax(L, N-1), rangemax(0, R));
}
if(R < l || r < L) return make_pair(-2*INF, -1);
else if(L <= l && r <= R)
{
return mx;
}
else
{
pair<long long, int> A = max(left->rangemax(L, R), right->rangemax(L, R));
A.first += lp;
// cerr << "returning " << A.first << ' ' << A.second << " for rangemax " << L << ' ' << R << '\n';
return A;
}
}
};
segtree R;
vector<int> pos;
void init(int k, vector<int> r)
{
N = r.size();
K = k;
segtree R(0, N-1); //R stores the array r, if an index is dead its value is INF
segtree S(0, N-1); //S[i] is equal to the number of indices j in [i-K, i-1] that have R[j] >= 1
// including dead
//If the index i is dead, S[i] is equal to -1.
/*
R: if index i is alive, R[i] = r[i]
if index i is dead, R[i] = >=INF
S: if index i is alive:
if R[i] == 0:
S[i] = #(j in [i-K, i-1], R[j] >= 1) (including dead stuff)
else:
S[i] = -INF + #(j in [i-K, i-1], R[j] >= 1)
if index i is dead: S[i] = -INF + ?
*/
vector<int> h_greedy;
for(int i = 0; i < N; i++)
{
R.add(i, i, +r[i]);
if(r[i] >= 1)
S.add(i+1, i+K-1, +1);
if(r[i] != 0)
S.add(i, i, -INF);
}
// cerr << "check\n";
// for(int i = 0; i < N; i++) cerr << R.rangemin(i, i).first << ' ' << R.rangemin(i, i).second << '\n';
// cerr << '\n';
for(int t = 0; t < N; t++)
{
// cerr << "\n\n";
// for(int i = 0; i < N; i++) cerr << S.rangemax(i, i).first << ' ' << S.rangemax(i, i).second << " | ";
// cerr << '\n';
// for(int i = 0; i < N; i++) cerr << R.rangemax(i, i).first << ' ' << R.rangemax(i, i).second << " | ";
// cerr << '\n';
// cerr << "t = " << t << ", ";
// cerr << "IMPORTANT CALL!\n";
// cerr << S.mx.first << ' ' << S.mx.second << '\n';
pair<long long, int> p = S.rangemax(0, N-1);
int I = p.second;
h_greedy.push_back(I);
// cerr << "I = " << I << '\n';
R.add(I, I, +INF);
S.add(I, I, -INF);
S.add(I+1, I+K-1, +1);
vector<int> newzeros;
// R.add(I+1, I+K-1, -1);
R.add(I-K+1, I-1, -1);
while(1)
{
// for(int i = 0; i < N; i++) cerr << R.rangemin(i, i).second << ' ';
// cerr << '\n';
pair<long long, int> q = R.rangemin(I-K+1, I-1);
if(q.first > 0) break;
// cerr << "q = " << q.second << '\n';
newzeros.push_back(q.second);
R.add(q.second, q.second, +1);
}
for(int z: newzeros)
{
R.add(z, z, -1);
S.add(z, z, +INF);
}
for(int z: newzeros)
S.add(z+1, z+K-1, -1);
}
//h_greedy is an ordering of the plants decreasingly by height.
H = vector<int>(N);
for(int i = 0; i < N; i++)
H[ h_greedy[i] ] = N-1-i;
for(int i = 0; i < N; i++) cerr << H[i] << ' ';
cerr << '\n';
vector<int> h_pos(N);
for(int i = 0; i < N; i++)
h_pos[ H[i] ] = i;
segtree HT(0, N-1);
for(int i = 0; i < N; i++)
HT.add(i, i, +INF);
left_high = new int*[N];
right_high = new int*[N];
for(int i = 0; i < N; i++)
{
left_high[i] = new int[logN];
right_high[i] = new int[logN];
}
for(int g = N-1; g >= 0; g--)
{
int p = h_pos[g];
pair<long long, int> rh = HT.rangemin(p+1, p+K-1);
if(rh.first >= INF)
right_high[p][0] = p;
else
right_high[p][0] = rh.second;
pair<long long, int> lh = HT.rangemin(p-K+1, p-1);
if(lh.first >= INF)
left_high[p][0] = p;
else
right_high[p][0] = lh.second;
HT.add(p, p, -INF + H[g]);
}
for(int e = 1; e < logN; e++)
{
for(int i = 0; i < N; i++)
{
left_high[i][e] = left_high[ left_high[i][e-1] ][e-1];
right_high[i][e] = right_high[ right_high[i][e-1] ][e-1];
}
}
for(int i = 0; i < N; i++) cerr << left_high[i][0] << ' ' << right_high[i][0] << '\n';
}
bool query_right(int x, int y) //is there an increasing path from x to y?
{
// for(int e = logN - 1; e >= 0; e--)
// {
// if(dist(x, right_high[x][e]) + dist(right_high[x][e], y) > dist(x, y)) continue;
// if(H[ right_high[x][e] ] >= H[y]) continue;
// x = right_high[x][e];
// }
//
// if(min(dist(x, y), dist(y, x)) < K)
// {
// return H[x] < H[y];
// }
// else
// {
// return 0;
// }
while(1)
{
if(min(dist(x, y), dist(y, x)) < K)
{
return H[x] < H[y];
}
else if(right_high[x][0] != x)
{
if(H[ right_high[x][0] ] < H[y])
x = right_high[x][0];
else
return 0;
}
else
{
return 0;
}
}
}
bool query_left(int x, int y)
{
// cerr << "query left " << x << ' ' << y << '\n';
// cerr << "left high " << x << ' ' << left_high[x][0] << '\n';
// for(int e = logN - 1; e >= 0; e--)
// {
// if(dist(left_high[x][e], x) + dist(y, left_high[x][e]) > dist(y, x)) continue;
// if(H[ left_high[x][e] ] >= H[y]) continue;
// x = left_high[x][e];
// }
//
// if(min(dist(x, y), dist(y, x)) < K)
// {
// return H[x] < H[y];
// }
// else
// {
// return 0;
// }
while(1)
{
if(min(dist(x, y), dist(y, x)) < K)
{
return H[x] < H[y];
}
else if(left_high[x][0] != x)
{
if(H[ left_high[x][0] ] < H[y])
x = left_high[x][0];
else
return 0;
}
else
{
return 0;
}
}
}
int compare_plants(int x, int y)
{
if(query_left(y, x)) return 1;
else if(query_right(y, x)) return 1;
else if(query_left(x, y)) return -1;
else if(query_right(x, y)) return -1;
else return 0;
}
