Submission #818051

#	Time	Username	Problem	Language	Result	Execution time	Memory
818051		oscar1f	Comparing Plants (IOI20_plants)	C++17	14 / 100	4054 ms	51424 KiB

plants

#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 (a==b) {
        return 0;
    }
    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]=nbVal;
        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<<" : ";
        for (int k=0;k<MAX_LOG;k++) {
            cout<<fils[i][0][k]<<" ";
        }
        cout<<"\t";
        for (int k=0;k<MAX_LOG;k++) {
            cout<<fils[i][1][k]<<" ";
        }
        cout<<endl;
    }
    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;
        while (pos<=fils[pos][1][0] and fils[pos][1][0]<=y) {
            pos=fils[pos][1][0];
        }
        /*for (int k=MAX_LOG-1;k>=0;k--) {
            //cout<<pos<<" ";
            nouv=fils[pos][1][k];
            if (pos<=nouv and nouv<=y) {
                pos=nouv;
            }
        }*/
        //cout<<pos<<"\t";
        if (dist(pos,y,1)<nbSuiv and rep[pos]>=rep[y]) {
            return 1;
        }
        pos=x;
        while (fils[pos][0][0]!=nbVal and ((fils[pos][0][0]<=pos and pos<y) or (fils[pos][0][0]>=y and pos>y))) {
            pos=fils[pos][0][0];
        }
        /*for (int k=MAX_LOG-1;k>=0;k--) {
            nouv=fils[pos][0][k];
            if (nouv!=nbVal and ((nouv<=pos and pos<y) or (nouv>=y and pos>y))) {
                pos=nouv;
            }
        }*/
        //cout<<pos<<endl;
        if (dist(pos,y,0)<nbSuiv and rep[pos]>=rep[y]) {
            return 1;
        }
        return 0;
    }
    else {
        pos=y;
        while (fils[pos][0][0]<=pos and fils[pos][0][0]>=pos) {
            pos=fils[pos][0][0];
        }
        /*for (int k=MAX_LOG-1;k>=0;k--) {
            nouv=fils[pos][0][k];
            if (nouv<=pos and nouv>=x) {
                pos=nouv;
            }
        }*/
        //cout<<pos<<" ";
        if (dist(pos,x,0)<nbSuiv and rep[pos]>=rep[x]) {
            return -1;
        }
        pos=y;
        while (fils[pos][1][0]!=nbVal and ((fils[pos][1][0]>=pos and pos>x) or (fils[pos][1][0]<=x and pos<x))) {
            pos=fils[pos][1][0];
        }
        /*for (int k=MAX_LOG-1;k>=0;k--) {
            nouv=fils[pos][1][k];
            if (nouv!=nbVal and ((nouv>=pos and pos>x) or (nouv<=x and pos<x))) {
                pos=nouv;
            }
        }*/
        //cout<<pos<<endl;
        if (dist(pos,x,1)<nbSuiv and rep[pos]>=rep[x]) {
            return -1;
        }
        return 0;
    }
}

Compilation message (stderr)

plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:244:13: warning: unused variable 'nouv' [-Wunused-variable]
  244 |     int pos,nouv;
      |             ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25