Submission #659668

#	Time	Username	Problem	Language	Result	Execution time	Memory
659668		Richem	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	3035 ms	14300 KiB

elephants

#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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3