oj.uz

Submission #818046

# Submission time Handle Problem Language Result Execution time Memory
818046 2023-08-10T00:34:42 Z oscar1f Comparing Plants (IOI20_plants) C++17
27 / 100
 724 ms 58280 KB 
#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;
        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;
        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;
        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;
        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;
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10580 KB Output is correct
2 Correct 4 ms 10580 KB Output is correct
3 Correct 4 ms 10580 KB Output is correct
4 Correct 4 ms 10580 KB Output is correct
5 Correct 6 ms 10600 KB Output is correct
6 Incorrect 62 ms 13352 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10580 KB Output is correct
2 Correct 4 ms 10580 KB Output is correct
3 Correct 4 ms 10580 KB Output is correct
4 Correct 4 ms 10580 KB Output is correct
5 Correct 4 ms 10540 KB Output is correct
6 Correct 7 ms 10776 KB Output is correct
7 Correct 64 ms 14344 KB Output is correct
8 Correct 6 ms 10708 KB Output is correct
9 Correct 7 ms 10836 KB Output is correct
10 Correct 74 ms 16220 KB Output is correct
11 Correct 64 ms 16112 KB Output is correct
12 Correct 64 ms 16432 KB Output is correct
13 Correct 64 ms 16332 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10580 KB Output is correct
2 Correct 4 ms 10580 KB Output is correct
3 Correct 4 ms 10580 KB Output is correct
4 Correct 4 ms 10580 KB Output is correct
5 Correct 4 ms 10540 KB Output is correct
6 Correct 7 ms 10776 KB Output is correct
7 Correct 64 ms 14344 KB Output is correct
8 Correct 6 ms 10708 KB Output is correct
9 Correct 7 ms 10836 KB Output is correct
10 Correct 74 ms 16220 KB Output is correct
11 Correct 64 ms 16112 KB Output is correct
12 Correct 64 ms 16432 KB Output is correct
13 Correct 64 ms 16332 KB Output is correct
14 Correct 104 ms 19636 KB Output is correct
15 Correct 701 ms 55280 KB Output is correct
16 Correct 108 ms 19584 KB Output is correct
17 Correct 724 ms 55144 KB Output is correct
18 Correct 540 ms 54740 KB Output is correct
19 Correct 702 ms 58280 KB Output is correct
20 Correct 618 ms 55204 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10580 KB Output is correct
2 Correct 4 ms 10580 KB Output is correct
3 Incorrect 64 ms 13700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10580 KB Output is correct
2 Correct 4 ms 10580 KB Output is correct
3 Incorrect 4 ms 10516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10580 KB Output is correct
2 Correct 4 ms 10536 KB Output is correct
3 Correct 4 ms 10580 KB Output is correct
4 Incorrect 4 ms 10580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10580 KB Output is correct
2 Correct 4 ms 10580 KB Output is correct
3 Correct 4 ms 10580 KB Output is correct
4 Correct 4 ms 10580 KB Output is correct
5 Correct 6 ms 10600 KB Output is correct
6 Incorrect 62 ms 13352 KB Output isn't correct
7 Halted 0 ms 0 KB -