#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int) k; i++)
const int N = 2e6 + 10;
int n2, lo[N], hi[N], mid[N];
bitset<N> flag;
int segMin[N << 2], segMax[N << 2];
inline int mergeMin(int a , int b) {
if (a == -1) return b;
if (b == -1) return a;
return mid[a] < mid[b] ? a : b;
}
inline int mergeMax(int a, int b) {
if (a == -1) return b;
if (b == -1) return a;
return mid[a] < mid[b] ? b : a;
}
inline int mergeMin(int id) {
return mergeMin(segMin[id << 1] , segMin[id << 1| 1]);
}
inline int mergeMax(int id) {
return mergeMax(segMax[id <<1 ] , segMax[id << 1 | 1]);
}
inline void build() {
rep(i , 0 , n2)
segMin[i + n2] = segMax[i + n2] = i;
for (int i = n2 - 1; i; i--) {
segMin[i] = mergeMin(i);
segMax[i] = mergeMax(i);
}
}
inline void segDeactive(int p) {
p += n2;
segMin[p] = segMax[p] = -1;
while (p > 1) {
p >>= 1;
segMin[p] = mergeMin(p);
segMax[p] = mergeMax(p);
}
}
inline int segGetMin(int l , int r) {
int best = -1;
for (l += n2, r += n2; l < r; l >>= 1, r >>= 1) {
if (l & 1) best = mergeMin(best , segMin[l++]);
if (r & 1) best = mergeMin(best , segMin[--r]);
}
return best;
}
inline int segGetMax(int l , int r) {
int best = -1;
for (l += n2, r += n2; l < r; l >>= 1, r >>= 1) {
if (l & 1) best = mergeMax(best , segMax[l++]);
if (r & 1) best = mergeMax(best , segMax[--r]);
}
return best;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
fill(hi , hi + n, 1e5 + 10);
n2 = n;
rep(att , 0 , 18) {
flag.reset();
rep(i , 0 , n)
mid[i] = lo[i] + hi[i] >> 1;
build();
for (int i = k - 1; ~i; i--) {
if (op[i] == 1) {
while (true) {
int id = segGetMin(left[i] , right[i] + 1);
if (id == -1 || mid[id] > height[i]) break;
flag[id] = true;
segDeactive(id);
}
}
else {
while (true) {
int id = segGetMax(left[i] , right[i] + 1);
if (id == -1 || mid[id] <= height[i]) break;
segDeactive(id);
}
}
}
rep(i , 0 , n) {
if (flag[i] || !mid[i])
lo[i] = mid[i];
else
hi[i] = mid[i];
}
}
rep(i , 0 , n) finalHeight[i] = lo[i];
return;
}
