oj.uz

Submission #818065

# Submission time Handle Problem Language Result Execution time Memory
818065 2023-08-10T01:11:37 Z oscar1f Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 55980 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);
    }
}

bool estEntre(int a,int b,int c) {
    if (b==nbVal) {
        return false;
    }
    if (b<a) {
        b+=nbVal;
    }
    if (c<a) {
        c+=nbVal;
    }
    if (b>=a and c>=b) {
        return true;
    }
    return false;
}

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 (estEntre(pos,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 (estEntre(y,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!=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 (estEntre(x,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 (estEntre(pos,fils[pos][1][0],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

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

Subtask #1
0 / 5.0

# 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 Correct 4 ms 10592 KB Output is correct
4 Correct 4 ms 10580 KB Output is correct
5 Correct 4 ms 10580 KB Output is correct
6 Correct 45 ms 13444 KB Output is correct
7 Correct 153 ms 17304 KB Output is correct
8 Correct 367 ms 54336 KB Output is correct
9 Correct 510 ms 54360 KB Output is correct
10 Correct 1554 ms 54400 KB Output is correct
11 Execution timed out 4066 ms 55188 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 5 ms 10620 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 10580 KB Output is correct
6 Correct 7 ms 10836 KB Output is correct
7 Correct 55 ms 14356 KB Output is correct
8 Correct 6 ms 10692 KB Output is correct
9 Correct 8 ms 10836 KB Output is correct
10 Correct 63 ms 14472 KB Output is correct
11 Correct 1158 ms 14328 KB Output is correct
12 Correct 1034 ms 14528 KB Output is correct
13 Correct 54 ms 14360 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 5 ms 10620 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 10580 KB Output is correct
6 Correct 7 ms 10836 KB Output is correct
7 Correct 55 ms 14356 KB Output is correct
8 Correct 6 ms 10692 KB Output is correct
9 Correct 8 ms 10836 KB Output is correct
10 Correct 63 ms 14472 KB Output is correct
11 Correct 1158 ms 14328 KB Output is correct
12 Correct 1034 ms 14528 KB Output is correct
13 Correct 54 ms 14360 KB Output is correct
14 Correct 95 ms 17308 KB Output is correct
15 Correct 694 ms 51484 KB Output is correct
16 Correct 98 ms 17364 KB Output is correct
17 Correct 688 ms 51304 KB Output is correct
18 Execution timed out 4065 ms 51412 KB Time limit exceeded
19 Halted 0 ms 0 KB -

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 Correct 263 ms 13728 KB Output is correct
4 Execution timed out 4054 ms 55980 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.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 10580 KB Output is correct
6 Correct 8 ms 10708 KB Output is correct
7 Correct 17 ms 11604 KB Output is correct
8 Correct 15 ms 11616 KB Output is correct
9 Correct 19 ms 11600 KB Output is correct
10 Correct 14 ms 11604 KB Output is correct
11 Correct 16 ms 11604 KB Output is correct
12 Correct 16 ms 11604 KB Output is correct
13 Correct 13 ms 11572 KB Output is correct

Subtask #6
0 / 15.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 10708 KB Output is correct
6 Correct 529 ms 53624 KB Output is correct
7 Correct 1566 ms 53808 KB Output is correct
8 Correct 715 ms 54028 KB Output is correct
9 Correct 784 ms 54116 KB Output is correct
10 Correct 1048 ms 53628 KB Output is correct
11 Execution timed out 4062 ms 54248 KB Time limit exceeded
12 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 5 ms 10580 KB Output is correct
3 Correct 4 ms 10592 KB Output is correct
4 Correct 4 ms 10580 KB Output is correct
5 Correct 4 ms 10580 KB Output is correct
6 Correct 45 ms 13444 KB Output is correct
7 Correct 153 ms 17304 KB Output is correct
8 Correct 367 ms 54336 KB Output is correct
9 Correct 510 ms 54360 KB Output is correct
10 Correct 1554 ms 54400 KB Output is correct
11 Execution timed out 4066 ms 55188 KB Time limit exceeded
12 Halted 0 ms 0 KB -