#include "elephants.h"
#include <vector>
#include <iostream>
using namespace std;
const int MAX_ELEPH = 150042, TAILLE_BLOC = 442, INF = 1e9+42;
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;
}
}
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 dicho(int deb, int fin, int val, int idBloc) {
while(deb < fin) {
int milieu = (deb + fin) / 2;
if(bloc[idBloc][milieu].pos <= val) {
deb = milieu;
}
else {
fin = milieu-1;
}
}
return deb;
}
int update(int i, int y) {
enleve(quelBloc[i], i);
int ouAjout = 0;
while(ouAjout < nbBloc-1 && bloc[ouAjout+1][0].pos < y) {
ouAjout++;
}
ajout(ouAjout, i, y);
if(nbDansBloc[quelBloc[i]] == 0 || nbDansBloc[ouAjout] == TAILLE_BLOC-2) {
recalcul();
}
int rep = 0;
int idBloc = 0;
int curId = 0;
while(idBloc < nbBloc) {
rep += nbRequis[idBloc][curId];
int finPhoto = finPhotoBloc[idBloc][curId];
while(idBloc < nbBloc && bloc[idBloc][nbDansBloc[idBloc]-1].pos <= finPhoto) {
idBloc++;
}
if(idBloc == nbBloc) {
break;
}
//int curId = dicho(0, nbDansBloc[idBloc-1], fin, idBloc);
int deb = 0, fin = nbDansBloc[idBloc-1];
while(deb < fin) {
int milieu = (deb + fin) / 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();
retu
while(1) {
int a,b;
cin >> a >> b;
cout << update(a, b) << endl;
}
}
*/
| # |
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 |
| # |
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 |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
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 |
1 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 |
Execution timed out |
9089 ms |
1596 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 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 |
Execution timed out |
9089 ms |
1596 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 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 |
Execution timed out |
9089 ms |
1596 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
