#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct segtree {
struct node {
int Max;
int Min;
node() {
Max = 1e9;
Min = -1e9;
}
};
vector<node> tree;
node op(node a, node b) {
node res;
res.Min = max(a.Min, b.Min);
res.Max = min(a.Max, b.Max);
if (res.Min > res.Max) {
if (b.Min > a.Max) {
res.Max = b.Min;
}
if (b.Max < a.Min) {
res.Min = b.Max;
}
}
return res;
}
node queryAll() {
return tree[1];
}
void update(int v, int rl, int rr, int pos, node x) {
if (rl == rr) {
tree[v] = x; return;
}
int rm = (rl + rr) / 2;
if (pos <= rm) update(v*2, rl, rm, pos, x);
else update(v*2+1, rm+1, rr, pos, x);
tree[v] = op(tree[v*2], tree[v*2+1]);
}
};
struct event {
int t;
int index;
int x;
bool start; // 1start; 0end
bool type; // 1max; 0min
};
bool compare(event a, event b) {
return vector<int>{a.t, a.index, a.x, a.start, a.type} < vector<int>{b.t, b.index, b.x, b.start, b.type};
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
deque<event> events;
for (int i=0; i<k; i++) {
event blub;
blub.index = i;
blub.x = height[i];
blub.type = op[i]-1;
blub.t = left[i];
blub.start = 1;
events.push_back(blub);
blub.t = right[i]+1;
blub.start = 0;
events.push_back(blub);
}
sort(events.begin(), events.end(), compare);
segtree seg;
seg.tree.assign(k*4, segtree::node());
for (int i = 0; i<n; i++) {
while (events[0].t == i) {
if (events[0].start == 0) {
seg.update(1, 0, k-1, events[0].index, segtree::node());
}
else {
segtree::node newOp;
if (events[0].type) {newOp.Max = events[0].x; newOp.Min = -1e9;}
else {newOp.Min = events[0].x; newOp.Max = 1e9;}
seg.update(1, 0, k-1, events[0].index, newOp);
}
events.pop_front();
}
finalHeight[i] = max(0, seg.queryAll().Min);
}
return;
}
