#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define F(i, n) for(int i = 0; i < (n); i++)
using pii = pair<int, int>;
pii merge(pii a, pii b) {
if(a.second < b.first) {
return {b.first, b.first};
} else if(b.second < a.first) {
return {b.second, b.second};
} else {
return {max(a.first, b.first), min(a.second, b.second)};
}
}
struct segtree {
pii segtree[1 << 21];
int segtree_size = 1;
pii zero = {0, INT_MAX};
void init(int n) {
segtree_size = 1;
while(segtree_size < n) {
segtree_size <<= 1;
}
F(i, 2 * segtree_size) {
segtree[i] = zero;
}
}
pii add(pii a, pii b) {
return merge(a, b);
}
pii get(int i, int window_l, int window_r, int l, int r) {
if(l <= window_l && window_r <= r) {
return segtree[i];
} else if(window_l <= l && l <= window_r || window_l <= r && r <= window_r) {
int m = (window_l + window_r) / 2;
return add(get(i * 2 + 0, window_l,m,l,r), get(i * 2 + 1,m + 1,window_r,l,r));
} else {
return zero;
}
}
pii get(int l, int r) {
if(l > r) {
return zero;
}
return get(1, 0, segtree_size - 1, l, r);
}
void set(int i, pii data) {
i += segtree_size;
segtree[i] = data;
i /= 2;
while(i > 0) {
segtree[i] = add(segtree[i * 2 + 0], segtree[i * 2 + 1]);
i /= 2;
}
}
} ohio;
enum evt_type {
ENTRY,
EXIT
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
vector<pair<int, int>> intervals;
vector<tuple<int, evt_type, int>> evts;
ohio.init(k);
F(i, k) {
if(op[i] == 1) {
intervals.emplace_back(height[i], INT_MAX);
} else if(op[i] == 2) {
intervals.emplace_back(0, height[i]);
} else {
assert(false);
}
evts.emplace_back(left[i], ENTRY, i);
evts.emplace_back(right[i] + 1, EXIT, i);
}
sort(evts.begin(), evts.end());
auto it = evts.begin();
F(i, n) {
while(it != evts.end() && get<0>(*it) == i) {
auto [wall_idx, evt_type, interval_idx] = *it;
if(evt_type == ENTRY) {
ohio.set(interval_idx, intervals[interval_idx]);
} else {
ohio.set(interval_idx, ohio.zero);
}
++it;
}
finalHeight[i] = merge({0, 0}, ohio.segtree[1]).first;
}
}
