oj.uz

Submission #542559

# Submission time Handle Problem Language Result Execution time Memory
542559 2022-03-26T22:58:56 Z Leo121 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 2897 ms 11840 KB 
#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 + 1] = X[i];
        porordenar[i + 1] = posiciones[i + 1];
    }
    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
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1928 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 204 ms 3776 KB Output is correct
8 Correct 245 ms 4040 KB Output is correct
9 Correct 311 ms 5256 KB Output is correct
10 Correct 312 ms 5048 KB Output is correct
11 Correct 353 ms 4980 KB Output is correct
12 Correct 506 ms 5140 KB Output is correct
13 Correct 338 ms 4828 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1928 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 204 ms 3776 KB Output is correct
8 Correct 245 ms 4040 KB Output is correct
9 Correct 311 ms 5256 KB Output is correct
10 Correct 312 ms 5048 KB Output is correct
11 Correct 353 ms 4980 KB Output is correct
12 Correct 506 ms 5140 KB Output is correct
13 Correct 338 ms 4828 KB Output is correct
14 Correct 268 ms 4704 KB Output is correct
15 Correct 419 ms 4804 KB Output is correct
16 Correct 814 ms 5720 KB Output is correct
17 Correct 897 ms 6224 KB Output is correct
18 Correct 972 ms 6120 KB Output is correct
19 Correct 527 ms 6140 KB Output is correct
20 Correct 874 ms 6368 KB Output is correct
21 Correct 884 ms 6236 KB Output is correct
22 Correct 540 ms 5996 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1928 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 204 ms 3776 KB Output is correct
8 Correct 245 ms 4040 KB Output is correct
9 Correct 311 ms 5256 KB Output is correct
10 Correct 312 ms 5048 KB Output is correct
11 Correct 353 ms 4980 KB Output is correct
12 Correct 506 ms 5140 KB Output is correct
13 Correct 338 ms 4828 KB Output is correct
14 Correct 268 ms 4704 KB Output is correct
15 Correct 419 ms 4804 KB Output is correct
16 Correct 814 ms 5720 KB Output is correct
17 Correct 897 ms 6224 KB Output is correct
18 Correct 972 ms 6120 KB Output is correct
19 Correct 527 ms 6140 KB Output is correct
20 Correct 874 ms 6368 KB Output is correct
21 Correct 884 ms 6236 KB Output is correct
22 Correct 540 ms 5996 KB Output is correct
23 Correct 2258 ms 9048 KB Output is correct
24 Correct 2512 ms 8968 KB Output is correct
25 Correct 1622 ms 8996 KB Output is correct
26 Correct 2111 ms 8936 KB Output is correct
27 Correct 2127 ms 9260 KB Output is correct
28 Correct 449 ms 4868 KB Output is correct
29 Correct 419 ms 4812 KB Output is correct
30 Correct 455 ms 4892 KB Output is correct
31 Correct 425 ms 4860 KB Output is correct
32 Correct 1963 ms 8396 KB Output is correct
33 Correct 1614 ms 8288 KB Output is correct
34 Correct 1671 ms 8392 KB Output is correct
35 Correct 1554 ms 8392 KB Output is correct
36 Correct 1525 ms 8316 KB Output is correct
37 Correct 2119 ms 9024 KB Output is correct
38 Correct 1742 ms 8276 KB Output is correct
39 Correct 1627 ms 8416 KB Output is correct
40 Correct 1883 ms 8192 KB Output is correct
41 Correct 2863 ms 8600 KB Output is correct
42 Correct 2897 ms 11840 KB Output is correct