#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
typedef long long ll;
typedef pair<int, int> point;
const int off = 1 << 19, inf = 1e9;
point T[2 * off];
point Merge(point A, point B) {
point ret = A;
ret.first = min(ret.first, B.second);
ret.first = max(ret.first, B.first);
ret.second = min(A.second, B.second);
return ret;
}
void upd(int x, point v) {
x += off;
T[x] = v;
for(x /= 2; x; x /= 2) {
T[x] = Merge(T[x * 2], T[x * 2 + 1]);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
vector<pair<point, int>> e;
REP(i, k) {
e.push_back({{left[i], 0}, i});
e.push_back({{right[i], 2}, i});
}
REP(i, n) {
e.push_back({{i, 1}, i});
}
REP(i, 2 * off) T[i] = {0, inf};
sort(e.begin(), e.end());
for(auto p: e) {
if(p.first.second == 0) {
point v = {0, inf};
int i = p.second;
if(op[i] == 1) {
v.first = height[i];
}
else {
v.second = height[i];
}
upd(i, v);
}
else if(p.first.second == 1) {
finalHeight[p.second] = T[1].first;
}
else {
upd(p.second, {0, inf});
}
}
}
