#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
struct ST {
vt<int> st_max, st_min, lz;
ST(int n) {
st_max.resize(n << 2);
st_min.resize(n << 2);
lz.resize(n << 2, -1);
}
#define lc i << 1
#define rc lc | 1
void push(int i) {
if (lz[i] < 0)
return;
st_max[lc] = st_max[rc] = st_min[lc] = st_min[rc] = lz[lc] = lz[rc] = lz[i];
lz[i] = -1;
}
void pull(int i) {
st_max[i] = max(st_max[lc], st_max[rc]);
st_min[i] = min(st_min[lc], st_min[rc]);
}
void chmax(int ql, int qr, int v, int i = 1, int tl = 0, int tr = -1) {
if (tr < 0)
tr += size(st_max) >> 2;
if (tl > qr || tr < ql || st_min[i] >= v)
return;
if (ql <= tl && tr <= qr && st_max[i] < v)
st_max[i] = st_min[i] = lz[i] = v;
else {
push(i);
int tm = tl + tr >> 1;
chmax(ql, qr, v, lc, tl, tm);
chmax(ql, qr, v, rc, tm+1, tr);
pull(i);
}
}
void chmin(int ql, int qr, int v, int i = 1, int tl = 0, int tr = -1) {
if (tr < 0)
tr += size(st_max) >> 2;
if (tl > qr || tr < ql || st_max[i] <= v)
return;
if (ql <= tl && tr <= qr && st_min[i] > v)
st_max[i] = st_min[i] = lz[i] = v;
else {
push(i);
int tm = tl + tr >> 1;
chmin(ql, qr, v, lc, tl, tm);
chmin(ql, qr, v, rc, tm+1, tr);
pull(i);
}
}
int qry(int p, int i = 1, int tl = 0, int tr = -1) {
tr += size(st_max) >> 2;
while (tl < tr) {
push(i);
int tm = tl + tr >> 1;
if (p <= tm)
i = lc, tr = tm;
else
i = rc, tl = tm + 1;
}
return st_max[i];
}
#undef lc
#undef rc
};
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
ST st(N);
FOR(i, 0, K-1) {
if (op[i] == 1)
st.chmax(left[i], right[i], height[i]);
else
st.chmin(left[i], right[i], height[i]);
}
FOR(i, 0, N-1)
finalHeight[i] = st.qry(i);
}
