#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,TAILLE_MAX=(1<<19);
int nbVal,nbSuiv,valCour,nouv,idNouv;
vector<int> val;
int rep[MAX_VAL];
noeud lazy[TAILLE_MAX];
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;
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();
}
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));
}
/*for (int i=0;i<nbVal;i++) {
cout<<rep[i]<<" ";
}
cout<<endl;*/
}
int compare_plants(int x, int y) {
if (rep[x]>rep[y]) {
return 1;
}
else {
return -1;
}
return 0;
}
