#include <bits/stdc++.h>
#include "plants.h"
#define ll long long
#define inf (ll) 1e17
#define dbg(x) cerr << #x << ' ' << x << endl;
using namespace std;
vector<ll> p;
ll n;
void printvec(vector<ll>& vec)
{
for (auto &&e : vec)
{
cout << e << ' ';
}
cout << endl;
}
ll maxn=2e5;
vector<ll> tree(4*maxn+4);
vector<ll> lazy(4*maxn+4);
vector<ll> chajara(4*maxn+4);
vector<ll> kassoul(4*maxn+4);
void prop(ll node, ll l, ll r, vector<ll>& tre, vector<ll>& laz)
{
tre[node]+=laz[node];
if(l==r)
{
laz[node]=0;
return;
}
laz[node*2+1]+=laz[node];
laz[node*2+2]+=laz[node];
laz[node]=0;
}
void update(ll node, ll l, ll r, ll x, ll y, ll val, vector<ll>& tre, vector<ll>& laz)
{
prop(node,l, r, tre, laz);
if(max(l,x) > min(r,y)) return;
if(x<=l && r<=y)
{
laz[node]+=val;
prop(node,l,r,tre, laz);
return;
}
ll mid=(l+r)/2;
update(node*2+1,l,mid,x,y,val, tre, laz);
update(node*2+2,mid+1,r,x,y,val, tre, laz);
tre[node]=min(tre[node*2+1],tre[node*2+2]);
}
ll query(ll node, ll l, ll r, ll x, ll y, vector<ll>& tre, vector<ll>& laz)
{
prop(node,l,r, tre, laz);
if(max(l,x) > min(r,y)) return inf;
if(x<=l && r<=y)
{
return tre[node];
}
ll mid=(l+r)>>1;
return min(query(node*2+1,l,mid,x,y, tre, laz),query(node*2+2,mid+1,r,x,y, tre, laz));
}
void decrease(ll l, ll r)
{
if(l<=r)
{
update(0,0,n-1,l,r,-1,tree, lazy);
}
else
{
update(0,0,n-1,l,n-1,-1, tree, lazy);
if(r>=0)
update(0,0,n-1,0,r,-1, tree, lazy);
}
}
ll findsmallest(ll l, ll r, vector<ll>& tre, vector<ll>& laz)
{
ll ans=r+1;
ll oldl=l;
while(l<=r)
{
ll mid=(l+r)>>1;
ll vl=query(0,0,n-1,oldl,mid, tre, laz);
if(vl==0)
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
return ans;
}
void init(int k, std::vector<int> r)
{
n=r.size();
p.resize(n);
vector<bool> vis(n);
for (int i=0;i<n;i++)
{
r[i]=k-1-r[i];
}
for (int i=0;i<n;i++)
{
if(r[i]==0)
{
if(i+k<=n)
{
update(0,0,n-1,i+1,i+k-1,1,chajara, kassoul);
}
else
{
if(i<n-1)update(0,0,n-1,i+1,n-1,1,chajara,kassoul);
update(0,0,n-1,0,(i+k-1)%n,1,chajara,kassoul);
}
}
}
for (int i=0;i<n;i++)
{
update(0,0,n-1,i,i,r[i], tree, lazy);
}
for (int i=0;i<n;i++)
{
ll ind=findsmallest(0,n-1,tree,lazy);
ll index=ind+k;
if(ind<n-1) index=findsmallest(ind+1,n-1,chajara,kassoul);
if(index<n)
{
ll vl=findsmallest(index,n-1,tree,lazy);
if(vl!=n)
{
ind=vl;
}
}
vis[ind]=true;
update(0,0,n-1,ind,ind,inf,tree,lazy);
p[ind]=i;
decrease((ind-k+1+n)%n,ind-1);
if(ind+k<=n)
{
update(0,0,n-1,ind+1,ind+k-1,-1,chajara, kassoul);
}
else
{
if(ind<n-1)update(0,0,n-1,ind+1,n-1,-1,chajara,kassoul);
update(0,0,n-1,0,(ind+k-1)%n,-1,chajara,kassoul);
}
ll j=max(0ll,ind-k+1);
while(j<=ind-1)
{
j=findsmallest(j,ind-1,tree,lazy);
if(j==ind) break;
if(j+k<=n)
{
update(0,0,n-1,j+1,j+k-1,1,chajara, kassoul);
}
else
{
if(j<n-1)update(0,0,n-1,j+1,n-1,1,chajara,kassoul);
update(0,0,n-1,0,(j+k-1)%n,1,chajara,kassoul);
}
j++;
}
if(ind-k+1 < 0)
{
j=ind-k+1+n;
while(j<n)
{
j=findsmallest(j,n-1,tree,lazy);
if(j==n) break;
if(j+k<=n)
{
update(0,0,n-1,j+1,j+k-1,1,chajara, kassoul);
}
else
{
if(j<n-1)update(0,0,n-1,j+1,n-1,1,chajara,kassoul);
update(0,0,n-1,0,(j+k-1)%n,1,chajara,kassoul);
}
j++;
}
}
}
}
int compare_plants(int x, int y)
{
if(p[x]<p[y]) return -1;
else return 1;
}
// we can use binary search to find each element when its r is 0, so total complexity is O(nlog(n))
