#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e6;
const int inf = 1 << 30;
static int v[nmax + 1];
struct str {
int mn, mx;
str () {
mn = inf;
mx = -inf;
}
} aint[4 * nmax + 1];
void propaga (int nod) {
for (int i = 0; i < 2; ++ i) {
aint[2 * nod + i].mx = min(aint[2 * nod + i].mx, aint[nod].mn);
aint[2 * nod + i].mn = min(aint[2 * nod + i].mn, aint[nod].mn);
aint[2 * nod + i].mx = max(aint[2 * nod + i].mx, aint[nod].mx);
aint[2 * nod + i].mn = max(aint[2 * nod + i].mn, aint[nod].mx);
}
aint[nod] = str();
}
void update_max (int nod, int x, int y, int st, int dr, int val) {
if (st <= x && y <= dr) {
aint[nod].mx = max(aint[nod].mx, val);
aint[nod].mn = max(aint[nod].mn, val);
return ;
}
propaga(nod);
int mij = (x + y) / 2;
if (st <= mij)
update_max(2 * nod, x, mij, st, dr, val);
if (mij < dr)
update_max(2 * nod + 1, mij + 1, y, st, dr, val);
}
void update_min (int nod, int x, int y, int st, int dr, int val) {
if (st <= x && y <= dr) {
aint[nod].mx = min(aint[nod].mx, val);
aint[nod].mn = min(aint[nod].mn, val);
return ;
}
propaga(nod);
int mij = (x + y) / 2;
if (st <= mij)
update_min(2 * nod, x, mij, st, dr, val);
if (mij < dr)
update_min(2 * nod + 1, mij + 1, y, st, dr, val);
}
void dfs (int nod, int x, int y) {
if (x == y) {
v[x] = max(aint[nod].mx, min(0, aint[nod].mn));
return ;
}
propaga(nod);
int mij = (x + y) / 2;
dfs(2 * nod, x, mij);
dfs(2 * nod + 1, mij + 1, y);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < k; ++ i) {
if (op[i] == 1)
update_max(1, 0, n - 1, left[i], right[i], height[i]);
else
update_min(1, 0, n - 1, left[i], right[i], height[i]);
}
dfs(1, 0, n - 1);
for (int i = 0; i < n; ++ i)
finalHeight[i] = v[i];
return;
}
