#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct node {
bool lazy;
int alto;
int bajo;
bool ultimo;
};
const int maxn = 2e6;
node st[4 * maxn + 1];
int valu[maxn];
void push(int nodo, int l, int r){
if(!st[nodo].lazy){
return;
}
if(l == r){
if(st[nodo].alto == -1){
valu[l] = min(valu[l], st[nodo].bajo);
}
else if(st[nodo].bajo == -1){
valu[l] = max(valu[l], st[nodo].alto);
}
else{
if(st[nodo].ultimo){
valu[l] = min(valu[l], st[nodo].bajo);
valu[l] = max(valu[l], st[nodo].alto);
}
else{
valu[l] = max(valu[l], st[nodo].alto);
valu[l] = min(valu[l], st[nodo].bajo);
}
}
}
else{
if((st[nodo].bajo != -1 && st[nodo].alto != -1 && st[nodo].ultimo) || st[nodo].alto == -1){
if(!st[nodo * 2].lazy){
st[nodo * 2] = {1, -1, st[nodo].bajo, 0};
}
else{
if(st[nodo * 2].bajo > st[nodo].bajo || st[nodo * 2].alto > st[nodo].bajo || st[nodo * 2].bajo == -1){
st[nodo * 2].ultimo = 0;
st[nodo * 2].bajo = st[nodo].bajo;
}
}
if(!st[nodo * 2 + 1].lazy){
st[nodo * 2 + 1] = {1, -1, st[nodo].bajo, 0};
}
else{
if(st[nodo * 2 + 1].bajo > st[nodo].bajo || st[nodo * 2 + 1].alto > st[nodo].bajo || st[nodo * 2 + 1].bajo == -1){
st[nodo * 2 + 1].ultimo = 0;
st[nodo * 2 + 1].bajo = st[nodo].bajo;
}
}
if(st[nodo].alto != -1){
if(st[nodo * 2].alto < st[nodo].alto || st[nodo * 2].bajo > st[nodo].alto || st[nodo * 2].alto == -1){
st[nodo * 2].ultimo = 1;
st[nodo * 2].alto = st[nodo].alto;
}
if(st[nodo * 2 + 1].alto < st[nodo].alto || st[nodo * 2 + 1].bajo > st[nodo].alto || st[nodo * 2 + 1].alto == -1){
st[nodo * 2 + 1].ultimo = 1;
st[nodo * 2 + 1].alto = st[nodo].alto;
}
}
}
else{
if(!st[nodo * 2].lazy){
st[nodo * 2] = {1, st[nodo].alto, -1, 1};
}
else{
if(st[nodo * 2].alto < st[nodo].alto || st[nodo * 2].bajo > st[nodo].alto || st[nodo * 2].alto == -1){
st[nodo * 2].ultimo = 1;
st[nodo * 2].alto = st[nodo].alto;
}
}
if(!st[nodo * 2 + 1].lazy){
st[nodo * 2 + 1] = {1, st[nodo].alto, -1, 1};
}
else{
if(st[nodo * 2 + 1].alto < st[nodo].alto || st[nodo * 2 + 1].bajo > st[nodo].alto || st[nodo * 2 + 1].alto == -1){
st[nodo * 2 + 1].ultimo = 1;
st[nodo * 2 + 1].alto = st[nodo].alto;
}
}
if(st[nodo].bajo != -1){
if(st[nodo * 2].bajo > st[nodo].bajo || st[nodo * 2].alto > st[nodo].bajo || st[nodo * 2].bajo == -1){
st[nodo * 2].ultimo = 0;
st[nodo * 2].bajo = st[nodo].bajo;
}
if(st[nodo * 2 + 1].bajo > st[nodo].bajo || st[nodo * 2 + 1].alto > st[nodo].bajo || st[nodo * 2 + 1].bajo == -1){
st[nodo * 2 + 1].ultimo = 0;
st[nodo * 2 + 1].bajo = st[nodo].bajo;
}
}
}
}
st[nodo] = {0, -1, -1, 0};
}
void built(int nodo, int l, int r){
st[nodo] = {0, -1, -1, 0};
if(l == r){
return;
}
int mitad = (l + r) / 2;
built(nodo * 2, l, mitad);
built(nodo * 2 + 1, mitad + 1, r);
}
void update(int nodo, int l, int r, int a, int b, bool tipo, int val){
push(nodo, l, r);
if(r < a || l > b){
return;
}
if(l >= a && r <= b){
if(tipo){
if(l == r){
valu[l] = max(valu[l], val);
return;
}
if(!st[nodo * 2].lazy){
st[nodo * 2] = {1, val, -1, 1};
}
else{
if(st[nodo * 2].alto < val || st[nodo * 2].bajo > val || st[nodo * 2].alto == -1){
st[nodo * 2].ultimo = 1;
st[nodo * 2].alto = val;
}
}
if(!st[nodo * 2 + 1].lazy){
st[nodo * 2 + 1] = {1, val, -1, 1};
}
else{
if(st[nodo * 2 + 1].alto < val || st[nodo * 2 + 1].bajo > val || st[nodo * 2 + 1].alto == -1){
st[nodo * 2 + 1].ultimo = 1;
st[nodo * 2 + 1].alto = val;
}
}
return;
}
else{
if(l == r){
valu[l] = min(valu[l], val);
return;
}
if(!st[nodo * 2].lazy){
st[nodo * 2] = {1, -1, val, 0};
}
else{
if(st[nodo * 2].bajo > val || st[nodo * 2].alto > val || st[nodo * 2].bajo == -1){
st[nodo * 2].ultimo = 0;
st[nodo * 2].bajo = val;
}
}
if(!st[nodo * 2 + 1].lazy){
st[nodo * 2 + 1] = {1, -1, val, 0};
}
else{
if(st[nodo * 2 + 1].bajo > val || st[nodo * 2 + 1].alto > val || st[nodo * 2 + 1].bajo == -1){
st[nodo * 2 + 1].ultimo = 0;
st[nodo * 2 + 1].bajo = val;
}
}
return;
}
}
int mitad = (l + r) / 2;
update(nodo * 2, l, mitad, a, b, tipo, val);
update(nodo * 2 + 1, mitad + 1, r, a, b, tipo, val);
}
void query(int nodo, int l, int r){
push(nodo, l, r);
if(l == r){
return;
}
int mitad = (l + r) / 2;
query(nodo * 2, l, mitad);
query(nodo * 2 + 1, mitad + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
built(1, 0, n - 1);
for(int i = 0; i < k; ++ i){
bool opcion = (op[i] == 1);
update(1, 0, n - 1, left[i], right[i], opcion, height[i]);
}
query(1, 0, n - 1);
for(int i = 0; i < n; ++ i){
finalHeight[i] = valu[i];
}
}
