#include <bits/stdc++.h>
#include <algorithm>
#include <set>
using namespace std;
const int N_MAX = 2000002;
const int K_MAX = 500002;
const int V_MAX = 100002;
const int ST_MAX = (1 << 18) + 2;
set <int> q_ind_up[V_MAX], q_ind_down[V_MAX];
int st_up[ST_MAX], st_down[ST_MAX];
void build(int v, int s, int e) {
st_up[v] = st_down[v] = -1;
if (s == e) {
return;
}
int m = (s + e) / 2;
build(v*2, s, m);
build(v*2+1, m+1, e);
}
void update(int v, int s, int e, int p, int val, bool up) {
if (s == e){
if (up) st_up[v] = val;
else st_down[v] = val;
return;
}
int m = (s + e) / 2;
if (p <= m) update(v*2, s, m, p, val, up);
else update(v*2+1, m+1, e, p, val, up);
if (up) st_up[v] = max(st_up[v*2], st_up[v*2+1]);
else st_down[v] = max(st_down[v*2], st_down[v*2+1]);
}
int get(int v, int s, int e, int l, int r, bool up) {
if (l > r) return -1;
if (s == l && e == r) {
if (up) return st_up[v];
return st_down[v];
}
int m = (s + e) / 2;
int lft = get(v*2, s, m, l, min(r, m), up);
int rgt = get(v*2+1, m+1, e, max(l, m+1), r, up);
return max(lft, rgt);
}
int get_set_last(const set<int> &s) {
int res = -1;
if (s.size() > 0){
auto it = s.end();
--it;
res = (*it);
}
return res;
}
void add_flag(int height, int q_ind, bool up) {
set<int> &ind_set = up ? q_ind_up[height] : q_ind_down[height];
int old = get_set_last(ind_set);
ind_set.insert(q_ind);
int nw = get_set_last(ind_set);
if (old != nw) {
update(1, 0, V_MAX-2, height, nw, up);
}
}
void remove_flag(int height, int q_ind, bool up) {
set<int> &ind_set = up ? q_ind_up[height] : q_ind_down[height];
int old = get_set_last(ind_set);
ind_set.erase(q_ind);
int nw = get_set_last(ind_set);
if (old != nw) {
update(1, 0, V_MAX-2, height, nw, up);
}
}
bool check_lb(int lb) {
int down_ind_max = get(1, 0, V_MAX-2, 0, lb-1, false);
int up_ind_max = get(1, 0, V_MAX-2, lb, V_MAX-2, true);
if (up_ind_max == -1) {
return false;
}
if (down_ind_max == -1) {
return true;
}
return up_ind_max > down_ind_max;
}
int find_height() {
int S = 0, E = V_MAX-2;
int res = 0;
while(S <= E) {
int M = (S+E) / 2;
if (check_lb(M)) {
res = M;
S = M+1;
}
else {
E = M-1;
}
}
return res;
}
int find_height2(int v, int s, int e, int up_ind_carry, int down_ind_carry) {
if (s == e) {
return s;
}
int m = (s + e) / 2;
int down_ind_max = max(st_down[v*2], down_ind_carry);
int up_ind_max = max(st_up[v*2+1], up_ind_carry);
if (up_ind_max == -1) {
return find_height2(v*2, s, m, up_ind_carry, down_ind_carry);
}
if (down_ind_max == -1) {
return find_height2(v*2+1, m+1, e, up_ind_carry, down_ind_carry);
}
if (up_ind_max > down_ind_max) {
return find_height2(v*2+1, m+1, e, up_ind_carry, max(down_ind_carry, down_ind_max));
}
else {
return find_height2(v*2, s, m, max(up_ind_carry, up_ind_max), down_ind_carry);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
build(1, 0, V_MAX-2);
vector < vector<int> > flags(n);
for(int i = 0; i < k; ++i) {
flags[left[i]].push_back(i);
if (right[i] < n - 1) flags[right[i]+1].push_back(-i-1);
}
for (int i = 0; i < n; ++i) {
for (const auto &q_ind: flags[i]) {
if (q_ind >= 0) {
add_flag(height[q_ind], q_ind, op[q_ind] == 1);
}
else {
remove_flag(height[-q_ind-1], -q_ind-1, op[-q_ind-1] == 1);
}
}
// finalHeight[i] = find_height();
finalHeight[i] = find_height2(1, 0, V_MAX-2, -1, -1);
}
}
