#include "elephants.h"
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i=int(a);i<=int(b);++i)
#define fora(i, a, b) for(int i=int(a);i>=int(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int lim = 15e4;
struct datos{
int pos, camaras, fin;
};
struct ura{
int tamanio = 0;
int l = 0, r = 1e9 + 1;
datos arre[800];
};
ura bloques[400];
int posiciones[lim + 2];
int porordenar[lim + 2];
int maxelementos[400];
int numbloques = 1;
int n, m = 0, l;
pii buscarnuevo(int x){
int li = 1, ls = numbloques, mitad, bloque = 0;
while(li <= ls){
mitad = (li + ls) / 2;
if((x >= bloques[mitad].l && x <= bloques[mitad].r) || (x > bloques[mitad - 1].r && x < bloques[mitad].l) || (x < bloques[mitad + 1].l && x > bloques[mitad].r)){
bloque = mitad;
break;
}
if(x > bloques[mitad].r){
li = mitad + 1;
}
else{
ls = mitad - 1;
}
}
li = 1, ls = bloques[bloque].tamanio;
int indice = 0;
while(li <= ls){
mitad = (li + ls) / 2;
if(bloques[bloque].arre[mitad].pos <= x){
indice = mitad;
li = mitad + 1;
}
else{
ls = mitad - 1;
}
}
return mp(bloque, indice);
}
pii buscar(int valor){
pii posicion = mp(0, 0);
int li = 1, ls = numbloques, mitad, bloque = 0;
while(li <= ls){
mitad = (li + ls) / 2;
if(valor >= bloques[mitad].l && valor <= bloques[mitad].r){
bloque = mitad;
break;
}
if(valor > bloques[mitad].r){
li = mitad + 1;
}
else{
ls = mitad - 1;
}
}
li = 1, ls = bloques[bloque].tamanio;
while(li <= ls){
mitad = (li + ls) / 2;
if(bloques[bloque].arre[mitad].pos == valor){
posicion = mp(bloque, mitad);
break;
}
if(valor > bloques[bloque].arre[mitad].pos){
li = mitad + 1;
}
else{
ls = mitad - 1;
}
}
return posicion;
}
int bsui(int bloque, int rango){
int li = 1, ls = bloques[bloque].tamanio, res = -1, mitad;
while(li <= ls){
mitad = (li + ls) / 2;
if(bloques[bloque].arre[mitad].pos > rango){
res = mitad;
ls = mitad - 1;
}
else{
li = mitad + 1;
}
}
return res;
}
int respuesta(){
int res = 0, abarcado, noabarcado;
res = bloques[1].arre[1].camaras;
abarcado = bloques[1].arre[1].fin;
forn(i, 2, numbloques){
noabarcado = bsui(i, abarcado);
if(noabarcado == -1){
continue;
}
res += bloques[i].arre[noabarcado].camaras;
abarcado = bloques[i].arre[noabarcado].fin;
}
return res;
}
void actualizar(int indice){
bloques[indice].arre[bloques[indice].tamanio].camaras = 1;
bloques[indice].arre[bloques[indice].tamanio].fin = bloques[indice].arre[bloques[indice].tamanio].pos + l;
int ultimo = bloques[indice].tamanio;
fora(i, bloques[indice].tamanio - 1, 1){
while(bloques[indice].arre[i].pos + l < bloques[indice].arre[ultimo].pos){
ultimo --;
}
bloques[indice].arre[i].camaras = (ultimo == bloques[indice].tamanio) ? 1 : 1 + bloques[indice].arre[ultimo + 1].camaras;
bloques[indice].arre[i].fin = (ultimo == bloques[indice].tamanio) ? bloques[indice].arre[i].pos + l : bloques[indice].arre[ultimo + 1].fin;
}
}
void armar(){
forn(i, 1, numbloques){
bloques[i].tamanio = 0;
}
int indicebloque = 1;
forn(i, 1, n){
if(bloques[indicebloque].tamanio == maxelementos[indicebloque]){
indicebloque ++;
}
bloques[indicebloque].tamanio ++;
bloques[indicebloque].arre[bloques[indicebloque].tamanio].pos = porordenar[i];
}
forn(i, 1, numbloques){
bloques[i].l = bloques[i].arre[1].pos;
bloques[i].r = bloques[i].arre[maxelementos[i]].pos;
actualizar(i);
}
}
void meter(){
int pos = 0;
forn(i, 1, numbloques){
forn(j, 1, bloques[i].tamanio){
porordenar[++ pos] = bloques[i].arre[j].pos;
}
}
}
void quitar(pii elefante){
bloques[elefante.fi].tamanio --;
forn(i, elefante.se, bloques[elefante.fi].tamanio){
bloques[elefante.fi].arre[i].pos = bloques[elefante.fi].arre[i + 1].pos;
}
bloques[elefante.fi].l = bloques[elefante.fi].arre[1].pos;
bloques[elefante.fi].r = bloques[elefante.fi].arre[bloques[elefante.fi].tamanio].pos;
actualizar(elefante.fi);
}
void insertar(pii elefante, int x){
bloques[elefante.fi].tamanio ++;
fora(i, bloques[elefante.fi].tamanio, elefante.se + 2){
bloques[elefante.fi].arre[i].pos = bloques[elefante.fi].arre[i - 1].pos;
}
bloques[elefante.fi].arre[elefante.se + 1].pos = x;
bloques[elefante.fi].l = bloques[elefante.fi].arre[1].pos;
bloques[elefante.fi].r = bloques[elefante.fi].arre[bloques[elefante.fi].tamanio].pos;
actualizar(elefante.fi);
}
void init(int N, int L, int X[])
{
n = N;
l = L;
numbloques = sqrt(n);
bloques[0].r = -1;
bloques[numbloques + 1].l = 1e9 + 1;
forn(i, 1, numbloques){
maxelementos[i] = n / numbloques;
}
forn(i, 1, n % numbloques){
maxelementos[i] ++;
}
forn(i, 0, n - 1){
posiciones[i] = X[i];
porordenar[i + 1] = posiciones[i];
}
armar();
}
int ind = 0, e, x;
pii dato;
int update(int i, int y)
{
m ++;
e = i + 1;
x = y;
if(ind + numbloques == m){
ind = m;
meter();
armar();
}
dato = buscar(posiciones[e]);
quitar(dato);
dato = buscarnuevo(x);
insertar(dato, x);
posiciones[e] = x;
return respuesta();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
