Submission #542558

#	Time	Username	Problem	Language	Result	Execution time	Memory
542558		Leo121	Dancing Elephants (IOI11_elephants)	C++14	0 / 100	1 ms	1876 KiB

elephants

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3