#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 offset;
lli st[400002];
void cambia(lli pos, lli val) {
if (val < 0) st[pos] = min(st[pos], abs(val));
else st[pos] = max(st[pos], val);
}
void push(lli pos) {
if (pos >= offset || st[pos] == 0) return;
if ((pos*2) >= offset) {
cambia(pos*2,st[pos]);
cambia((pos*2)+1,st[pos]);
}
else {
push(pos * 2);
st[pos*2] = st[pos];
push((pos * 2)+1);
st[(pos*2)+1] = st[pos];
}
st[pos] = 0;
}
void actualiza(lli pos, lli l, lli r, lli ini, lli fin, lli val) {
push(pos);
if (ini > r || fin < l) return;
if (l <= ini && fin <= r) {
if (ini == fin) cambia(pos,val);
else st[pos] = val;
}
else {
lli mitad=(ini+fin)/2;
actualiza(pos*2, l, r, ini, mitad, val);
actualiza((pos*2)+1, l, r, mitad+1, fin, val);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
offset = 1;
while (offset < n) offset *= 2;
rep(i,0,k-1) {
if (op[i] == 1) actualiza(1,left[i],right[i],0,offset-1,height[i]);
else actualiza(1,left[i],right[i],0,offset-1,-height[i]);
}
rep(i,1,offset-1) push(i);
rep(i,0,n-1) finalHeight[i] = st[i+offset];
return;
}
