#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<pair<int, int>> lazy;
vector<int> last;
void lz(int curin, int curl, int curr) {
if (curl == curr) {
if (last[curl] < lazy[curin].first) {
last[curl] = lazy[curin].first;
} else if (last[curl] > lazy[curin].second) {
last[curl] = lazy[curin].second;
}
lazy[curin] = {0, INT_MAX};
return;
}
if (lazy[curin * 2 + 1].second < lazy[curin].first) {
lazy[curin * 2 + 1] = {lazy[curin].first, lazy[curin].first};
} else if (lazy[curin].second < lazy[curin * 2 + 1].first) {
lazy[curin * 2 + 1] = {lazy[curin].second, lazy[curin].second};
} else {
lazy[curin * 2 + 1] = {max(lazy[curin].first, lazy[curin * 2 + 1].first),
min(lazy[curin].second, lazy[curin * 2 + 1].second)};
}
if (lazy[curin * 2 + 2].second < lazy[curin].first) {
lazy[curin * 2 + 2] = {lazy[curin].first, lazy[curin].first};
} else if (lazy[curin].second < lazy[curin * 2 + 2].first) {
lazy[curin * 2 + 2] = {lazy[curin].second, lazy[curin].second};
} else {
lazy[curin * 2 + 2] = {max(lazy[curin].first, lazy[curin * 2 + 2].first),
min(lazy[curin].second, lazy[curin * 2 + 2].second)};
}
lazy[curin] = {0, INT_MAX};
}
int ql, qr;
pair<int, int> qry;
void update(int curin = 0, int curl = 0, int curr = n - 1) {
lz(curin, curl, curr);
if (qr < curl || ql > curr) return;
if (ql <= curl && curr <= qr) {
lazy[curin] = qry;
lz(curin, curl, curr);
return;
}
update(curin * 2 + 1, curl, (curl + curr) / 2),
update(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
}
void ans(int curin = 0, int curl = 0, int curr = n - 1) {
lz(curin, curl, curr);
if (curl == curr) {
return;
}
ans(curin * 2 + 1, curl, (curl + curr) / 2),
ans(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
lazy = vector<pair<int, int>>(4 * n, {0, INT_MAX});
::n = n;
last = vector<int>(n, 0);
for (int i = 0; i < k; i++) {
ql = left[i], qr = right[i];
if (op[i] == 1) {
qry = {height[i], INT_MAX};
} else {
qry = {0, height[i]};
}
update();
}
ans();
for (int i = 0; i < n; i++) finalHeight[i] = last[i];
}
