Submission #421978

#	Time	Username	Problem	Language	Result	Execution time	Memory
421978		Ozy	Wall (IOI14_wall)	C++17	100 / 100	1166 ms	117992 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl

#define MAX 4500002
#define INF 1000000000

#define sube 1
#define baja 2


lli h[MAX], arriba[MAX], abajo[MAX];
lli ult,offset;

void push(lli nodo, lli s, lli e){
    lli hijo;

    if (s == e){
        h[nodo] = max(h[nodo], abajo[nodo]);
        h[nodo] = min(h[nodo], arriba[nodo]);
        abajo[nodo] = 0;
        arriba[nodo] = INF;
        return;
    }

    hijo = nodo * 2;
    arriba[hijo] = min(arriba[hijo], arriba[nodo]);
    abajo[hijo] = min(abajo[hijo], arriba[nodo]);
    arriba[hijo] = max(arriba[hijo], abajo[nodo]);
    abajo[hijo] = max(abajo[hijo], abajo[nodo]);

    hijo++;
    arriba[hijo] = min(arriba[hijo], arriba[nodo]);
    abajo[hijo] = min(abajo[hijo], arriba[nodo]);
    arriba[hijo] = max(arriba[hijo], abajo[nodo]);
    abajo[hijo] = max(abajo[hijo], abajo[nodo]);

    abajo[nodo] = 0;
    arriba[nodo] = INF;
}

void update(lli nodo, lli s, lli e, lli l, lli r, lli altura, lli tipo){
    push(nodo, s, e); // EMPUJA A LOS HIJOS

    if (s > r || e < l) return; // SI EL RANGO A ACTUALIZAR ESTA FUERA DE ESTE NO HAGAS NADA
    if (s == e){ // SI EL RANGO A ACTUALIZAR ES DE 1 ENTONCES ES HOJA, MODIFICA SU ALTURA
        if (tipo == sube) h[nodo] = max(h[nodo], altura);
        else if (tipo == baja) h[nodo] = min(h[nodo], altura);
    }
    if (s >= l && e <= r){ // SI EL RANGO ESTA COMPLETAMENTE CONTENIDO MODIFICA EL LIMITE
        if (tipo == sube) abajo[nodo] = max(abajo[nodo], altura);
        else if (tipo == baja) arriba[nodo] = min(arriba[nodo], altura);
        return;
    }

    lli mitad = (s + e) / 2;
    update(nodo * 2, s, mitad, l, r, altura, tipo);
    update(nodo * 2 + 1, mitad + 1, e, l, r, altura, tipo);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    offset = 1;
    while (offset <= n) offset *= 2;

    repa(i, offset - 1, 1){
        arriba[i] = INF;
        abajo[i] = 0;
    }

    rep(i, 0, k - 1) update(1, 0, offset - 1, left[i], right[i], height[i], op[i]);

    rep(i, 1, offset - 1) push(i, 0, n - 1);
    rep(i, offset, offset + n - 1) push(i, i, i);

    rep(i, offset, offset + n - 1) finalHeight[i - offset] = h[i];

    return;
}

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