#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
const int BIG = (int)(1e9);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int borne = 2*1000*1000 + 5;
int down[4*borne];
int up[4*borne];
int rep[borne];
void takeDown(int nod, int liv, int riv, int lop, int rop, int val);
void takeUp(int nod, int liv, int riv, int lop, int rop, int val);
void push(int nod, int liv, int riv)
{
int mm =(liv+riv) / 2;
takeDown(2*nod, liv, mm, liv, mm, down[nod]);
takeUp(2*nod, liv, mm, liv, mm, up[nod]);
takeDown(2*nod+1, mm+1, riv, mm+1, riv, down[nod]);
takeUp(2*nod+1, mm+1, riv, mm+1, riv, up[nod]);
down[nod] = BIG;
up[nod] = 0;
}
void takeDown(int nod, int liv, int riv, int lop, int rop, int val)
{
if (lop <= liv && riv <= rop) {
chmin(down[nod], val);
chmin(up[nod], down[nod]);
return;
}
if (lop > riv || rop < liv) return;
push(nod,liv,riv);
int mm = (liv+riv) / 2;
takeDown(2*nod, liv, mm, lop, rop, val);
takeDown(2*nod + 1, mm+1, riv, lop, rop, val);
}
void takeUp(int nod, int liv, int riv, int lop, int rop, int val)
{
if (lop <= liv && riv <= rop) {
chmax(up[nod], val);
chmax(down[nod], up[nod]);
return;
}
if (lop > riv || rop < liv) return;
push(nod,liv,riv);
int mm = (liv+riv) / 2;
takeUp(2*nod, liv, mm, lop, rop, val);
takeUp(2*nod + 1, mm+1, riv, lop, rop, val);
}
void con(int nod, int liv, int riv)
{
if (liv == riv) {
rep[liv] = min(down[nod], up[nod]);
return;
}
push(nod,liv,riv);
int mm = (liv+riv) / 2;
con(2*nod, liv, mm);
con(2*nod+1, mm+1, riv);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
form(i, 4*borne) down[i] = BIG;
form(i, k) {
if (op[i] == 1) takeUp(1, 0, n-1, left[i], right[i], height[i]);
else takeDown(1, 0, n-1, left[i], right[i], height[i]);
}
con(1, 0, n-1);
form(i, n) finalHeight[i] = rep[i];
}
