oj.uz

Submission #815705

# Submission time Handle Problem Language Result Execution time Memory
815705 2023-08-08T19:24:31 Z oscar1f Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 54752 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];
int dv[MAX_VAL];

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]);
    }
}

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 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;*/
}

void DFS(int pos) {
    if (pos<nbVal and dv[pos]==0) {
        dv[pos]=1;
        DFS(fils[pos][0][0]);
        DFS(fils[pos][1][0]);
    }
}

int compare_plants(int x, int y) {
    for (int i=0;i<nbVal;i++) {
        dv[i]=0;
    }
    if (rep[x]>rep[y]) {
        DFS(x);
        if (dv[y]==1) {
            return 1;
        }
        else {
            return 0;
        }
    }
    else {
        DFS(y);
        if (dv[x]==1) {
            return -1;
        }
        else {
            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 10576 KB Output is correct
6 Correct 49 ms 14420 KB Output is correct
7 Correct 449 ms 19524 KB Output is correct
8 Correct 2807 ms 54728 KB Output is correct
9 Correct 3082 ms 54752 KB Output is correct
10 Execution timed out 4049 ms 54484 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
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 5 ms 10580 KB Output is correct
4 Correct 5 ms 10580 KB Output is correct
5 Correct 5 ms 10580 KB Output is correct
6 Correct 26 ms 10868 KB Output is correct
7 Execution timed out 4062 ms 14036 KB Time limit exceeded
8 Halted 0 ms 0 KB -

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 5 ms 10580 KB Output is correct
4 Correct 5 ms 10580 KB Output is correct
5 Correct 5 ms 10580 KB Output is correct
6 Correct 26 ms 10868 KB Output is correct
7 Execution timed out 4062 ms 14036 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 5 ms 10580 KB Output is correct
3 Correct 1218 ms 13768 KB Output is correct
4 Execution timed out 4024 ms 53120 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 10608 KB Output is correct
4 Correct 5 ms 10568 KB Output is correct
5 Correct 5 ms 10580 KB Output is correct
6 Correct 6 ms 10708 KB Output is correct
7 Correct 21 ms 11536 KB Output is correct
8 Correct 49 ms 11524 KB Output is correct
9 Correct 41 ms 11628 KB Output is correct
10 Correct 53 ms 11524 KB Output is correct
11 Correct 25 ms 11604 KB Output is correct
12 Correct 45 ms 11556 KB Output is correct
13 Correct 63 ms 11528 KB Output is correct

Subtask #6
0 / 15.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 Correct 4 ms 10580 KB Output is correct
4 Correct 5 ms 10576 KB Output is correct
5 Correct 9 ms 10848 KB Output is correct
6 Correct 3652 ms 54048 KB Output is correct
7 Execution timed out 4054 ms 53832 KB Time limit exceeded
8 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 10576 KB Output is correct
6 Correct 49 ms 14420 KB Output is correct
7 Correct 449 ms 19524 KB Output is correct
8 Correct 2807 ms 54728 KB Output is correct
9 Correct 3082 ms 54752 KB Output is correct
10 Execution timed out 4049 ms 54484 KB Time limit exceeded
11 Halted 0 ms 0 KB -