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