oj.uz

Submission #659668

# Submission time Handle Problem Language Result Execution time Memory
659668 2022-11-18T22:45:04 Z Richem Dancing Elephants (IOI11_elephants) C++14
100 / 100
 3035 ms 14300 KB 
#include "elephants.h"
#include <vector>
#include <iostream>
 
using namespace std;
 
const int MAX_ELEPH = 150042, TAILLE_BLOC = 442;
 
struct Elephant{
    int id, pos;
};
 
int quelBloc[MAX_ELEPH];
Elephant bloc[TAILLE_BLOC][TAILLE_BLOC*2];
 
int nbDansBloc[TAILLE_BLOC] = {0};
 
int nbRequis[TAILLE_BLOC][TAILLE_BLOC*2];
int finPhotoBloc[TAILLE_BLOC][TAILLE_BLOC*2];
 
int nbElephant, taillePhoto;
int nbBloc;
 
vector<Elephant> nouv;
void reconstruire(int type) {
    if(type == 0) {
        for(int idBloc = 0; idBloc < nbBloc; idBloc++) {
            for(int id = 0; id < nbDansBloc[idBloc]; id++) {
                nouv.push_back({bloc[idBloc][id]});
            }
            nbDansBloc[idBloc] = 0;
        }
    }
    
    int curBloc = 0, curPos = 0;
 
    for(auto cur : nouv) {
        if(nbDansBloc[curBloc] == TAILLE_BLOC) {
            curBloc++;
            curPos = 0;
        }
        bloc[curBloc][curPos] = cur;
        nbDansBloc[curBloc]++;
        quelBloc[cur.id] = curBloc;
        curPos++;
    }
    nouv.clear();
}
 
void calcBloc(int idBloc) {
    int idFin = nbDansBloc[idBloc]-1;
    int posFin = bloc[idBloc][idFin].pos;
 
    for(int idCur = idFin; idCur >= 0; idCur--) {
        Elephant cur = bloc[idBloc][idCur];
        nbRequis[idBloc][idCur] = 1;
        finPhotoBloc[idBloc][idCur] = cur.pos + taillePhoto;
 
        if(cur.pos + taillePhoto < posFin) {
            while(cur.pos + taillePhoto < bloc[idBloc][idFin-1].pos) {
                idFin--;
            }
            nbRequis[idBloc][idCur] = nbRequis[idBloc][idFin] + 1;
            finPhotoBloc[idBloc][idCur] = finPhotoBloc[idBloc][idFin];
        }
    }
}
 
void recalcul() {
    reconstruire(0);
    for(int idBloc = 0; idBloc < nbBloc; idBloc++) {
        calcBloc(idBloc);
    }
}
 
void enleve(int idBloc, int idModif) {
    int ouModif = 0;
    for(int id = 0; id < nbDansBloc[idBloc]; id++) {
        if(bloc[idBloc][id].id == idModif) {
            ouModif = id;
        }
    }
 
    bloc[idBloc][ouModif] = {-1, -1};
    for(; ouModif < nbDansBloc[idBloc]-1; ouModif++) {
        swap(bloc[idBloc][ouModif], bloc[idBloc][ouModif+1]);
    }
    nbDansBloc[idBloc]--;
    calcBloc(idBloc);
}
 
void ajout(int idBloc, int idModif, int posModif) {
    int idCur = nbDansBloc[idBloc];
 
    while(1) {
        if(idCur > 0 && bloc[idBloc][idCur-1].pos > posModif) {
            swap(bloc[idBloc][idCur-1], bloc[idBloc][idCur]);
            idCur--;
        }
        else {
            break;
        }
    }
 
    quelBloc[idModif] = idBloc;
    nbDansBloc[idBloc]++;
    bloc[idBloc][idCur] = {idModif, posModif};
    calcBloc(idBloc);
}
 
 
void init(int N, int L, int X[]) {
    nbElephant = N, taillePhoto = L;
    nbBloc = (nbElephant + TAILLE_BLOC - 1) / TAILLE_BLOC;
 
    for(int cur = 0; cur < nbElephant; cur++) {
        nouv.push_back({cur, X[cur]});
    }
    reconstruire(1);
    recalcul();
}
 
int nbUpdate = 0;
 
int update(int i, int y) {
    nbUpdate++;
    enleve(quelBloc[i], i);
 
    int ouAjout = 0;
 
    while(ouAjout < nbBloc-1 && bloc[ouAjout+1][0].pos < y) {
        ouAjout++;
    }
 
    ajout(ouAjout, i, y);
 
    if(nbUpdate % (TAILLE_BLOC-2) == 0) {
        recalcul();
    }
 
    int rep = nbRequis[0][0];
    int posFin = finPhotoBloc[0][0];
 
    int curId = 0;

    for(int idBloc = 0; idBloc < nbBloc; idBloc++) {
        if(posFin >= bloc[idBloc][nbDansBloc[idBloc]-1].pos)
            continue;

        int deb = 0, fin = nbDansBloc[idBloc]-1;

        while(deb < fin) {
            int milieu = (deb + fin+1) / 2;
 
            if(bloc[idBloc][milieu].pos <= posFin) {
                deb = milieu;
            }
            else {
                fin = milieu-1;
            }
        }
        if(bloc[idBloc][deb].pos <= posFin) {
            deb++;
        }
        curId = deb;
        rep += nbRequis[idBloc][curId];
        posFin = finPhotoBloc[idBloc][curId];
    }
    
    /*
    while(idBloc < nbBloc) {
        rep += nbRequis[idBloc][curId];
        cout << rep << endl;
        int finPhoto = finPhotoBloc[idBloc][curId];
 
        while(idBloc < nbBloc && bloc[idBloc][nbDansBloc[idBloc]-1].pos <= finPhoto) {
            idBloc++;
        }
 
        if(idBloc == nbBloc) {
            break;
        }
 
        int deb = 0, fin = nbDansBloc[idBloc]-1;
 
        while(deb < fin) {
            int milieu = (deb + fin+1) / 2;
 
            if(bloc[idBloc][milieu].pos <= finPhoto) {
                deb = milieu;
            }
            else {
                fin = milieu-1;
            }
        }
 
        curId = deb;
    }
 
    */
    return rep;
}
 
int posDepart[MAX_ELEPH];
void input() {
    cin >> nbElephant >> taillePhoto;
 
    for(int i = 0; i < nbElephant; i++) {
        cin >> posDepart[i];
    }
}
 
void print() {
    for(int id = 0; id < nbBloc; id++) {
        for(int ah = 0; ah < nbDansBloc[id]; ah++) {
            cout << bloc[id][ah].id << " " << bloc[id][ah].pos << " " << nbRequis[id][ah] << " " << finPhotoBloc[id][ah] << endl;
        }
    }
}
/* 
int main() {
    input();
    init(nbElephant, taillePhoto, posDepart);
 
    recalcul();
 
    while(1) {
        int a,b;
        cin >> a >> b;
 
        cout << update(a, b) << endl;
        print();
        cout << endl;
    }
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 247 ms 1660 KB Output is correct
8 Correct 242 ms 2888 KB Output is correct
9 Correct 290 ms 4948 KB Output is correct
10 Correct 256 ms 4676 KB Output is correct
11 Correct 208 ms 4576 KB Output is correct
12 Correct 522 ms 4804 KB Output is correct
13 Correct 261 ms 4548 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 247 ms 1660 KB Output is correct
8 Correct 242 ms 2888 KB Output is correct
9 Correct 290 ms 4948 KB Output is correct
10 Correct 256 ms 4676 KB Output is correct
11 Correct 208 ms 4576 KB Output is correct
12 Correct 522 ms 4804 KB Output is correct
13 Correct 261 ms 4548 KB Output is correct
14 Correct 277 ms 3624 KB Output is correct
15 Correct 385 ms 3812 KB Output is correct
16 Correct 878 ms 5428 KB Output is correct
17 Correct 900 ms 6628 KB Output is correct
18 Correct 989 ms 6464 KB Output is correct
19 Correct 496 ms 6684 KB Output is correct
20 Correct 830 ms 6620 KB Output is correct
21 Correct 890 ms 6592 KB Output is correct
22 Correct 515 ms 6084 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 247 ms 1660 KB Output is correct
8 Correct 242 ms 2888 KB Output is correct
9 Correct 290 ms 4948 KB Output is correct
10 Correct 256 ms 4676 KB Output is correct
11 Correct 208 ms 4576 KB Output is correct
12 Correct 522 ms 4804 KB Output is correct
13 Correct 261 ms 4548 KB Output is correct
14 Correct 277 ms 3624 KB Output is correct
15 Correct 385 ms 3812 KB Output is correct
16 Correct 878 ms 5428 KB Output is correct
17 Correct 900 ms 6628 KB Output is correct
18 Correct 989 ms 6464 KB Output is correct
19 Correct 496 ms 6684 KB Output is correct
20 Correct 830 ms 6620 KB Output is correct
21 Correct 890 ms 6592 KB Output is correct
22 Correct 515 ms 6084 KB Output is correct
23 Correct 2246 ms 14264 KB Output is correct
24 Correct 2750 ms 14212 KB Output is correct
25 Correct 1823 ms 14268 KB Output is correct
26 Correct 2158 ms 14300 KB Output is correct
27 Correct 2425 ms 14124 KB Output is correct
28 Correct 1065 ms 5300 KB Output is correct
29 Correct 1018 ms 5304 KB Output is correct
30 Correct 1071 ms 5300 KB Output is correct
31 Correct 1016 ms 5308 KB Output is correct
32 Correct 1542 ms 13704 KB Output is correct
33 Correct 1035 ms 13076 KB Output is correct
34 Correct 1666 ms 13952 KB Output is correct
35 Correct 1184 ms 14140 KB Output is correct
36 Correct 709 ms 13660 KB Output is correct
37 Correct 2122 ms 14084 KB Output is correct
38 Correct 2016 ms 12928 KB Output is correct
39 Correct 1782 ms 13928 KB Output is correct
40 Correct 2235 ms 13028 KB Output is correct
41 Correct 2912 ms 13700 KB Output is correct
42 Correct 3035 ms 13944 KB Output is correct