#include<bits/stdc++.h>
#include "plants.h"
using namespace std;
struct noeud{
int deb,fin,somme=0;
pair<int,int> maxi;
};
const int MAX_VAL=200*1000+5,INFINI=1000*1000*1000,DECA=(1<<18),MAX_LOG=20;
int nbVal,nbSuiv,valCour,nouv,idNouv;
vector<int> val,ordre;
int rep[MAX_VAL];
noeud lazy[2*DECA];
pair<int,int> arbreMax[2*DECA];
int fils[MAX_VAL][2][MAX_LOG];
int dv[MAX_VAL];
void afficher() {
for (int i=1;i<8;i++) {
cout<<i<<" : "<<lazy[i].deb<<" "<<lazy[i].fin<<" "<<lazy[i].somme<<" "<<lazy[i].maxi.first<<" "<<lazy[i].maxi.second<<endl;
}
cout<<endl;
}
void creer(int pos,int debInter,int finInter) {
lazy[pos].deb=debInter;
lazy[pos].fin=finInter;
if (debInter==finInter) {
lazy[pos].maxi={val[debInter],debInter};
}
else {
int midInter=(debInter+finInter)/2;
creer(2*pos,debInter,midInter);
creer(2*pos+1,midInter+1,finInter);
lazy[pos].maxi=max(lazy[2*pos].maxi,lazy[2*pos+1].maxi);
}
}
void pushFlag(int pos) {
lazy[pos].maxi.first+=lazy[pos].somme;
if (lazy[pos].deb!=lazy[pos].fin) {
lazy[2*pos].somme+=lazy[pos].somme;
lazy[2*pos+1].somme+=lazy[pos].somme;
}
lazy[pos].somme=0;
}
int find(int pos,int debInter,int finInter) {
pushFlag(pos);
if (lazy[pos].deb>finInter or lazy[pos].fin<debInter) {
return -1;
}
if (lazy[pos].deb>=debInter and lazy[pos].fin<=finInter) {
if (lazy[pos].maxi.first!=nbSuiv-1) {
return -1;
}
return lazy[pos].maxi.second;
}
return max(find(2*pos,debInter,finInter),find(2*pos+1,debInter,finInter));
}
void supp(int pos,int posSup) {
pushFlag(pos);
if (lazy[pos].deb>posSup or lazy[pos].fin<posSup) {
return;
}
if (lazy[pos].deb==lazy[pos].fin) {
lazy[pos].maxi.first=-INFINI;
}
else {
supp(2*pos,posSup);
supp(2*pos+1,posSup);
lazy[pos].maxi=max(lazy[2*pos].maxi,lazy[2*pos+1].maxi);
}
}
void ajout(int pos,int debInter,int finInter) {
if (lazy[pos].deb>finInter or lazy[pos].fin<debInter) {
pushFlag(pos);
return;
}
if (lazy[pos].deb>=debInter and lazy[pos].fin<=finInter) {
lazy[pos].somme++;
pushFlag(pos);
return;
}
pushFlag(pos);
ajout(2*pos,debInter,finInter);
ajout(2*pos+1,debInter,finInter);
lazy[pos].maxi=max(lazy[2*pos].maxi,lazy[2*pos+1].maxi);
}
int verif(int pos) {
if (pos>=nbSuiv-1) {
return find(1,pos-nbSuiv+1,pos-1);
}
else {
if (pos!=0) {
return max(find(1,0,pos-1),find(1,pos-nbSuiv+1+nbVal,nbVal-1));
}
return find(1,pos-nbSuiv+1+nbVal,nbVal-1);
}
}
void extraire(int pos) {
while (verif(pos)!=-1) {
extraire(verif(pos));
}
idNouv++;
rep[pos]=idNouv;
ordre.push_back(pos);
supp(1,pos);
if (pos>=nbSuiv-1) {
ajout(1,pos-nbSuiv+1,pos);
}
else {
ajout(1,0,pos);
ajout(1,pos-nbSuiv+1+nbVal,nbVal-1);
}
//afficher();
}
pair<int,int> calcMax(int debInter,int finInter) {
if (debInter==finInter) {
return arbreMax[debInter];
}
if (debInter%2==1) {
return max(arbreMax[debInter],calcMax(debInter+1,finInter));
}
if (finInter%2==0) {
return max(arbreMax[finInter],calcMax(debInter,finInter-1));
}
return calcMax(debInter/2,finInter/2);
}
void maj(int pos) {
arbreMax[DECA+pos]={rep[pos],pos};
pos+=DECA;
while (pos>1) {
pos/=2;
arbreMax[pos]=max(arbreMax[2*pos],arbreMax[2*pos+1]);
}
}
void init(int k,vector<int> r) {
nbSuiv=k;
val=r;
nbVal=val.size();
creer(1,0,nbVal-1);
//afficher();
while (find(1,0,nbVal-1)!=-1) {
extraire(find(1,0,nbVal-1));
}
pair<int,int> meil;
for (int nouv:ordre) {
if (nouv>=nbSuiv-1) {
meil=calcMax(DECA+nouv-nbSuiv+1,DECA+nouv-1);
}
else {
if (nouv>0) {
meil=max(calcMax(DECA+0,DECA+nouv-1),calcMax(DECA+nouv-nbSuiv+1+nbVal,DECA+nbVal-1));
}
else {
meil=calcMax(DECA+nouv-nbSuiv+1+nbVal,DECA+nbVal-1);
}
}
if (meil.first>0) {
fils[nouv][0][0]=meil.second;
}
else {
fils[nouv][0][0]=nbVal;
}
if (nouv+nbSuiv-1<=nbVal-1) {
meil=calcMax(DECA+nouv+1,DECA+nouv+nbSuiv-1);
}
else {
if (nouv<nbVal-1) {
meil=max(calcMax(DECA+nouv+1,DECA+nbVal-1),calcMax(DECA+0,DECA+nouv+nbSuiv-1-nbVal));
}
else {
meil=calcMax(DECA+0,DECA+nouv+nbSuiv-1-nbVal);
}
}
if (meil.first>0) {
fils[nouv][1][0]=meil.second;
}
else {
fils[nouv][1][0]=nbVal;
}
maj(nouv);
}
/*for (int i=0;i<nbVal;i++) {
cout<<i<<" : "<<fils[i][0][0]<<" "<<fils[i][1][0]<<endl;
}
for (int i=0;i<nbVal;i++) {
cout<<rep[i]<<" ";
}
cout<<endl;*/
}
void DFS(int pos) {
if (pos<nbVal and dv[pos]==0) {
dv[pos]=1;
DFS(fils[pos][0][0]);
DFS(fils[pos][1][0]);
}
}
int compare_plants(int x, int y) {
for (int i=0;i<nbVal;i++) {
dv[i]=0;
}
if (rep[x]>rep[y]) {
DFS(x);
if (dv[y]==1) {
return 1;
}
else {
return 0;
}
}
else {
DFS(y);
if (dv[x]==1) {
return -1;
}
else {
return 0;
}
}
}
