#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int INF = (int) (1e5);
pair<int, int> neutre() {
return {0, INF};
}
pair<int, int> composi(pair<int, int> a, pair<int, int> b) {
if (b.first == b.second) {
int ham = max(min(b.first, a.second), a.first);
return {ham, ham};
}
if (a.first == a.second) {
return a;
}
if (b.first > a.second) {
auto brr = neutre();
brr.first = a.first;
return composi(brr, {a.second, a.second});
}
return {max(a.first, b.first), min(a.second, b.second)};
}
vector<pair<int, int>> seg;
vector<int> sus;
void apply(int node, int l, int r, int tl, int tr, pair<int, int> poudre) {
if (l == r)
sus[l] = node;
if (l > r)
return;
if (tl > tr)
return;
if (! ((l <= tl) && (tr <= r)))
return;
if ((l == tl) && (r == tr)) {
seg[node] = composi(poudre, seg[node]);
return;
}
int mid = (l + r) / 2;
seg[2 * node] = composi(seg[node], seg[2 * node]);
seg[2 * node + 1] = composi(seg[node], seg[2 * node + 1]);
seg[node] = neutre();
apply(2 * node, l, mid, tl, min(mid, tr), poudre);
apply(2 * node + 1, mid + 1, r, max(mid + 1, tl), tr, poudre);
return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
seg.assign(4 * n, neutre());
sus.assign(n, 0);
for (int i = 0; i < n; i ++)
apply(1, 0, n - 1, i, i, {0, 0});
for (int i = 0; i < k; i ++) {
auto brr = neutre();
if (op[i] == 1)
brr.first = height[i];
else
brr.second = height[i];
apply(1, 0, n - 1, left[i], right[i], brr);
}
for (int i = 0; i < n; i ++)
apply(1, 0, n - 1, i, i, neutre());
for (int i = 0; i < n; i ++)
finalHeight[i] = seg[sus[i]].first;
return;
}
