oj.uz

Submission #818055

# Submission time Handle Problem Language Result Execution time Memory
818055 2023-08-10T00:52:28 Z oscar1f Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 51432 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;
        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 or fils[pos][0][0]>=y) and pos<y) or (fils[pos][0][0]>=y and pos>y 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!=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 or fils[pos][1][0]<=x) and pos>x) or (fils[pos][1][0]<=x and pos<x and fils[pos][1][0]>=pos))) {
            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:244:13: warning: unused variable 'nouv' [-Wunused-variable]
  244 |     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 10580 KB Output is correct
4 Correct 4 ms 10580 KB Output is correct
5 Incorrect 4 ms 10580 KB Output isn't correct
6 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 10524 KB Output is correct
5 Correct 4 ms 10580 KB Output is correct
6 Correct 8 ms 10836 KB Output is correct
7 Correct 56 ms 14392 KB Output is correct
8 Correct 5 ms 10708 KB Output is correct
9 Correct 7 ms 10800 KB Output is correct
10 Correct 63 ms 14360 KB Output is correct
11 Correct 1004 ms 14324 KB Output is correct
12 Correct 51 ms 14612 KB Output is correct
13 Correct 54 ms 14392 KB Output is correct

Subtask #3
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 10524 KB Output is correct
5 Correct 4 ms 10580 KB Output is correct
6 Correct 8 ms 10836 KB Output is correct
7 Correct 56 ms 14392 KB Output is correct
8 Correct 5 ms 10708 KB Output is correct
9 Correct 7 ms 10800 KB Output is correct
10 Correct 63 ms 14360 KB Output is correct
11 Correct 1004 ms 14324 KB Output is correct
12 Correct 51 ms 14612 KB Output is correct
13 Correct 54 ms 14392 KB Output is correct
14 Correct 94 ms 17384 KB Output is correct
15 Correct 681 ms 51428 KB Output is correct
16 Correct 96 ms 17308 KB Output is correct
17 Correct 677 ms 51432 KB Output is correct
18 Execution timed out 4062 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 6 ms 10580 KB Output is correct
2 Correct 4 ms 10580 KB Output is correct
3 Incorrect 244 ms 13744 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
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 10544 KB Output is correct
4 Incorrect 4 ms 10580 KB Output isn't correct
5 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 10580 KB Output is correct
3 Correct 4 ms 10588 KB Output is correct
4 Correct 4 ms 10580 KB Output is correct
5 Incorrect 6 ms 10708 KB Output isn't correct
6 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 10580 KB Output is correct
4 Correct 4 ms 10580 KB Output is correct
5 Incorrect 4 ms 10580 KB Output isn't correct
6 Halted 0 ms 0 KB -