#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vint = vector<int>;
constexpr int maxn = 200'000;
bool k2check=false;
ll pref[maxn+5];
ll n;
ll k;
ll segmin[4*maxn];
ll segidx[4*maxn];
ll seglazy[4*maxn];
ll ans[maxn];
vint r;
void range_update(int id, int l, int r, int ql, int qr, ll delta) {
if(qr<=l||r<=ql)
return;
if(ql<=l&&r<=qr)
{
segmin[id]+=delta;
seglazy[id]+=delta;
return;
}
int lc=id*2,rc=id*2+1;
if(seglazy[id]!=0)
{
segmin[lc] += seglazy[id];
seglazy[lc] += seglazy[id];
segmin[rc] += seglazy[id];
seglazy[rc] += seglazy[id];
seglazy[id] = 0;
}
int m=l+(r-l)/2;
range_update(lc,l,m,ql,qr,delta);
range_update(rc,m,r,ql,qr,delta);
if(segmin[lc]<=segmin[rc])
{
segmin[id]=segmin[lc];
segidx[id]=segidx[lc];
}
else
{
segmin[id]=segmin[rc];
segidx[id]=segidx[rc];
}
}
pair<ll,int> range_query(int id, int l, int r, int ql, int qr)
{
//val idx
if(qr<=l||r<=ql)
return {LONG_LONG_MAX,-1};
if(ql<=l&&r<=qr)
return {segmin[id],segidx[id]};
int lc=id*2,rc=id*2+1;
if(seglazy[id]!=0)
{
segmin[lc]+=seglazy[id];
seglazy[lc]+=seglazy[id];
segmin[rc]+=seglazy[id];
seglazy[rc]+=seglazy[id];
seglazy[id]=0;
}
int m=l+(r-l)/2;
pair<ll,int> left=range_query(lc,l,m,ql,qr);
pair<ll,int> right=range_query(rc,m,r,ql,qr);
return (left.first<=right.first?left:right);
}
void init(int K, std::vector<int> R) {
k2check=false;
r=R;
k=K;
if(K==2)
k2check=true;
n=r.size();
if(k==2)
{
pref[0]=0;
for(int i=0;i<n;i++)
{
pref[i+1]=pref[i]+r[i];
}
return;
}
ll segsize=1;
while(segsize<n)
segsize<<=1;
for(int i=0;i<segsize*2;i++)
{
segmin[i]=LONG_LONG_MAX;
seglazy[i]=0;
segidx[i]=-1;
}
for(ll i=0;i<n;i++)
{
segmin[segsize+i]=r[i];
seglazy[segsize+i]=0;
segidx[segsize+i]=i;
}
for(ll i=segsize-1;i>0;i--)
{
seglazy[i]=0;
segmin[i]=min(segmin[i*2],segmin[i*2+1]);
if(segmin[i*2]<=segmin[i*2+1])
segidx[i]=segidx[i*2];
else
segidx[i]=segidx[i*2+1];
}
int x = n;
ll minval,minid;
while(true)
{
stack<ll> stk;
pair<ll,int> ret;
ret=range_query(1, 0, segsize, 0, n);
minval=ret.first;
minid=ret.second;
if(minval!=0)
break;
stk.push(minid);
while(!stk.empty())
{
ll curr=stk.top();
int l=curr-k+1,r=curr;
pair<ll,int> cand={LONG_LONG_MAX,-1};
if(l<0)
cand=(range_query(1,0,segsize,0,r).first<=range_query(1,0,segsize,n+l,n).first ? range_query(1,0,segsize,0,r) : range_query(1,0,segsize,n+l,n));
else
cand=range_query(1,0,segsize,l,r);
if(cand.first==0)
stk.push(cand.second);
else
{
ans[curr]=--x;
if(l<0)
{
range_update(1,0,segsize,0,r,-1);
range_update(1,0,segsize,n+l,n,-1);
}
else
range_update(1,0,segsize,l,r,-1);
range_update(1,0,segsize,curr,curr+1,LONG_LONG_MAX>>1);
stk.pop();
}
}
}
return;
}
int compare_plants(int x, int y) {
if(k2check)
{
if(pref[y]-pref[x]==0 || pref[n]-pref[y]+pref[x]==n-y+x)
return 1;
else if(pref[y]-pref[x]==y-x || pref[n]-pref[y]+pref[x]==0)
return -1;
else
return 0;
}
return (ans[x]<ans[y] ? -1 : 1);
}
