oj.uz

Submission #815671

# Submission time Handle Problem Language Result Execution time Memory
815671 2023-08-08T18:07:33 Z oscar1f Comparing Plants (IOI20_plants) C++17
44 / 100
 528 ms 22168 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,TAILLE_MAX=(1<<19);
int nbVal,nbSuiv,valCour,nouv,idNouv;
vector<int> val;
int rep[MAX_VAL];
noeud lazy[TAILLE_MAX];

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

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

    /*for (int i=0;i<nbVal;i++) {
        cout<<rep[i]<<" ";
    }
    cout<<endl;*/
}

int compare_plants(int x, int y) {
    if (rep[x]>rep[y]) {
        return 1;
    }
    else {
        return -1;
    }
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10568 KB Output is correct
2 Correct 5 ms 10576 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 4 ms 10452 KB Output is correct
5 Correct 5 ms 10572 KB Output is correct
6 Correct 7 ms 10580 KB Output is correct
7 Correct 54 ms 15272 KB Output is correct
8 Correct 6 ms 10580 KB Output is correct
9 Correct 7 ms 10676 KB Output is correct
10 Correct 66 ms 15348 KB Output is correct
11 Correct 59 ms 15196 KB Output is correct
12 Correct 52 ms 15476 KB Output is correct
13 Correct 60 ms 15440 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10568 KB Output is correct
2 Correct 5 ms 10576 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 4 ms 10452 KB Output is correct
5 Correct 5 ms 10572 KB Output is correct
6 Correct 7 ms 10580 KB Output is correct
7 Correct 54 ms 15272 KB Output is correct
8 Correct 6 ms 10580 KB Output is correct
9 Correct 7 ms 10676 KB Output is correct
10 Correct 66 ms 15348 KB Output is correct
11 Correct 59 ms 15196 KB Output is correct
12 Correct 52 ms 15476 KB Output is correct
13 Correct 60 ms 15440 KB Output is correct
14 Correct 83 ms 15968 KB Output is correct
15 Correct 491 ms 19792 KB Output is correct
16 Correct 89 ms 15876 KB Output is correct
17 Correct 483 ms 19760 KB Output is correct
18 Correct 296 ms 19292 KB Output is correct
19 Correct 419 ms 21352 KB Output is correct
20 Correct 414 ms 19820 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10452 KB Output is correct
2 Correct 5 ms 10468 KB Output is correct
3 Correct 50 ms 15068 KB Output is correct
4 Correct 304 ms 19704 KB Output is correct
5 Correct 386 ms 19276 KB Output is correct
6 Correct 452 ms 19276 KB Output is correct
7 Correct 528 ms 19524 KB Output is correct
8 Correct 505 ms 19788 KB Output is correct
9 Correct 326 ms 19008 KB Output is correct
10 Correct 373 ms 19480 KB Output is correct
11 Correct 198 ms 18948 KB Output is correct
12 Correct 344 ms 22168 KB Output is correct
13 Correct 295 ms 19144 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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