#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];
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]);
}
}
int dist(int a,int b,int tab) {
if (tab==1) {
if (b>a) {
return b-a;
}
else {
return nbVal-a+b;
}
}
else {
return nbVal-dist(a,b,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 j=0;j<=1;j++) {
fils[nbVal][j][0]=0;
for (int k=1;k<MAX_LOG;k++) {
for (int i=0;i<=nbVal;i++) {
if (fils[i][j][k-1]==nbVal or fils[fils[i][j][k-1]][j][k-1]==nbVal or dist(i,fils[i][j][k-1],j)+dist(fils[i][j][k-1],fils[fils[i][j][k-1]][j][k-1],j)>=nbVal) {
fils[i][j][k]=nbVal;
}
else {
fils[i][j][k]=fils[fils[i][j][k-1]][j][k-1];
}
}
}
}
/*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;*/
}
int compare_plants(int x, int y) {
int pos,nouv;
if (rep[x]>rep[y]) {
pos=x;
for (int k=MAX_LOG;k>=0;k--) {
nouv=fils[pos][1][k];
if (pos>=nouv and nouv<=y) {
pos=nouv;
}
}
if (dist(pos,y,1)<nbSuiv and rep[pos]>=rep[y]) {
return 1;
}
pos=x;
for (int k=MAX_LOG;k>=0;k--) {
nouv=fils[pos][0][k];
if (nouv!=nbVal and (nouv<=pos or nouv>=y)) {
pos=nouv;
}
}
if (dist(pos,y,0)<nbSuiv and rep[pos]>=rep[y]) {
return 1;
}
return 0;
}
else {
pos=y;
for (int k=MAX_LOG;k>=0;k--) {
nouv=fils[pos][0][k];
if (nouv<=pos and nouv>=x) {
pos=nouv;
}
}
if (dist(pos,x,0)<nbSuiv and rep[pos]>=rep[x]) {
return -1;
}
pos=y;
for (int k=MAX_LOG;k>=0;k--) {
nouv=fils[pos][1][k];
if (nouv!=nbVal and (nouv>=pos or nouv<=x)) {
pos=nouv;
}
}
if (dist(pos,x,1)<nbSuiv and rep[pos]>=rep[x]) {
return -1;
}
return 0;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10580 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10572 KB |
Output is correct |
| 3 |
Correct |
4 ms |
10580 KB |
Output is correct |
| 4 |
Correct |
5 ms |
10580 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
10580 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10572 KB |
Output is correct |
| 2 |
Correct |
4 ms |
10580 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
10572 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10572 KB |
Output is correct |
| 2 |
Correct |
4 ms |
10580 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
10572 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10580 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10580 KB |
Output is correct |
| 3 |
Incorrect |
68 ms |
15504 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10580 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10580 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
10580 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10580 KB |
Output is correct |
| 2 |
Correct |
4 ms |
10580 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
10580 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10580 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10572 KB |
Output is correct |
| 3 |
Correct |
4 ms |
10580 KB |
Output is correct |
| 4 |
Correct |
5 ms |
10580 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
10580 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
