Submission #1126791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126791		BlancaHM	Wall (IOI14_wall)	C++20	100 / 100	801 ms	78692 KiB

wall

#include <vector>
#include <iostream>

using namespace std;

int infinito = 2e9;


struct arbolDeSegmentos {
    vector<pair<int, int>> intervalos;

    arbolDeSegmentos(int n) {
        intervalos.assign(4 * n, make_pair(0, infinito));
    }
    
    void aplicarCambio(int x, int nuevoMinimo, int nuevoMaximo) {
        // Actualizamos el minimo
        intervalos[x].first = max(intervalos[x].first, nuevoMinimo);
    	intervalos[x].second = max(intervalos[x].second, intervalos[x].first);
    	// Actualizamos el maximo
    	intervalos[x].second = min(intervalos[x].second, nuevoMaximo);
    	intervalos[x].first = min(intervalos[x].first, intervalos[x].second);
    }
    
    void propagarCambio(int x, int l, int r) {
        if (l == r) return;
        aplicarCambio(2*x, intervalos[x].first, intervalos[x].second);
        aplicarCambio(2*x+1, intervalos[x].first, intervalos[x].second);
        intervalos[x] = make_pair(0, infinito);
    }

    void cambiarMinimo(
        int x,
        int l,
        int r,
        int inicioIntervalo,
        int finalIntervalo,
        int nuevoMinimo
    ) {
        if (r < inicioIntervalo || l > finalIntervalo) return;
        if (inicioIntervalo <= l && r <= finalIntervalo) {
            aplicarCambio(x, nuevoMinimo, infinito);
        } else {
            propagarCambio(x, l, r);
            int mid = l + (r - l) / 2;
            cambiarMinimo(
                2*x, l, mid, inicioIntervalo, finalIntervalo, nuevoMinimo
            );
            cambiarMinimo(
                2*x+1, mid+1, r, inicioIntervalo, finalIntervalo, nuevoMinimo
            );
        }
    }
    
    void cambiarMaximo(
        int x,
        int l,
        int r,
        int inicioIntervalo,
        int finalIntervalo,
        int nuevoMaximo
    ) {
        if (r < inicioIntervalo || l > finalIntervalo) return;
        if (inicioIntervalo <= l && r <= finalIntervalo) {
            aplicarCambio(x, 0, nuevoMaximo);
        } else {
            propagarCambio(x, l, r);
            int mid = l + (r - l) / 2;
            cambiarMaximo(
                2*x, l, mid, inicioIntervalo, finalIntervalo, nuevoMaximo
            );
            cambiarMaximo(
                2*x+1, mid+1, r, inicioIntervalo, finalIntervalo, nuevoMaximo
            );
        }
    }

    int encontrarAltura(int x, int l, int r, int indiceBuscado) {
        if (l == r) {
            return intervalos[x].first;  // == intervalos[x].second
        } else {
            propagarCambio(x, l, r);
            int mid = l + (r - l) / 2;
            if (indiceBuscado <= mid) {
                return encontrarAltura(2*x, l, mid, indiceBuscado);
            } else {
                return encontrarAltura(2*x+1, mid+1, r, indiceBuscado);
            }
        }
    }
};

void buildWall(
    int n,
    int k,
    int op[],
    int left[],
    int right[],
    int height[],
    int finalHeight[])
{
    arbolDeSegmentos arbol = arbolDeSegmentos(n);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            arbol.cambiarMinimo(1, 0, n-1, left[i], right[i], height[i]);
        } else {
            arbol.cambiarMaximo(1, 0, n-1, left[i], right[i], height[i]);
        }
    }
    
    for (int i = 0; i < n; i++) {
        finalHeight[i] = arbol.encontrarAltura(1, 0, n-1, i);
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39