#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
struct Node {
int min, max;
Node() { min = 0, max = 1e9; }
Node(int min, int max) : min(min), max(max) {}
};
struct SegmentTree {
Node T[N << 2];
#define mid ((l + r) >> 1)
void upd(int i, int l, int r, int p, Node x) {
if (l == r) {
T[i] = x; return;
}
if (mid >= p) upd(i << 1, l, mid, p, x);
else upd(i << 1 | 1, mid + 1, r, p, x);
T[i].min = max(T[i << 1].min, T[i << 1 | 1].min);
T[i].max = min(T[i << 1].max, T[i << 1 | 1].max);
}
int get1(int i, int l, int r, Node x) {
if (l == r) return l;
Node y;
y.min = max(x.min, T[i << 1 | 1].min);
y.max = min(x.max, T[i << 1 | 1].max);
if (y.min > y.max) {
return get1(i << 1 | 1, mid + 1, r, x);
}
return get1(i << 1, l, mid, y);
}
void get2(int i, int l, int r, int L, int R, Node& x) {
if (l > R || L > r) return;
if (L <= l && r <= R) {
x.min = max(x.min, T[i].min);
x.max = min(x.max, T[i].max);
return;
}
get2(i << 1, l, mid, L, R, x);
get2(i << 1 | 1, mid + 1, r, L, R, x);
}
#undef mid
} IT;
struct Event {
int v, p, x, y, t;
bool operator < (const Event& rhs) const {
return v < rhs.v;
}
};
void buildWall(int n, int m, int op[], int left[], int right[], int height[], int finalHeight[]) {
vector<Event> events;
for (int i = 0; i < m; ++i) {
events.push_back({left[i], i, height[i], op[i], 0});
events.push_back({right[i] + 1, i, height[i], op[i], 1});
}
sort(events.begin(), events.end());
int ptr = 0;
for (int i = 0; i < n; ++i) {
// cout << "#at " << i << '\n';
while (ptr < 2 * m && events[ptr].v <= i) {
if (events[ptr].t == 0) {
if (events[ptr].y == 2) {
// cout << "#add2 " << events[ptr].p << '\n';
IT.upd(1, 0, m - 1, events[ptr].p, Node(0, events[ptr].x));
}
else {
// cout << "#add1 " << events[ptr].p << '\n';
IT.upd(1, 0, m - 1, events[ptr].p, Node(events[ptr].x, 1e9));
}
}
else {
// cout << "#del " << events[ptr].p << '\n';
IT.upd(1, 0, m - 1, events[ptr].p, Node());
}
++ptr;
}
int v, L, R;
if (IT.T[1].min <= IT.T[1].max) {
L = IT.T[1].min, R = IT.T[1].max, v = 0;
}
else {
int p = IT.get1(1, 0, m - 1, Node());
// cout << "#p " << p << '\n';
v = height[p];
Node x = Node();
IT.get2(1, 0, m - 1, p + 1, m - 1, x);
L = x.min, R = x.max;
}
// cout << v << ' ' << L << ' ' << R << '\n';
if (v < L) finalHeight[i] = L;
else if (v > R) finalHeight[i] = R;
else finalHeight[i] = v;
}
}
