#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct Node {
int deb, fin, a, b;
};
const int T = 21, M = 1 << T, N = 2*M, INF = 1e9;
Node node[N];
void applyOp(int i, int a, int b) {
node[i].a = min(b, max(a, node[i].a));
node[i].b = min(b, max(a, node[i].b));
}
void update(int i, int deb, int fin, int a, int b) {
if(fin <= node[i].deb || node[i].fin <= deb)
return;
if(deb <= node[i].deb && node[i].fin <= fin) {
applyOp(i, a, b);
return;
}
applyOp(i*2, node[i].a, node[i].b);
applyOp(i*2+1, node[i].a, node[i].b);
node[i].a = -INF;
node[i].b = INF;
update(i*2, deb, fin, a, b);
update(i*2+1, deb, fin, a, b);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i < M; i++) {
node[i + M].deb = i;
node[i + M].fin = i+1;
}
for(int i = M-1; i > -1; i--) {
node[i].deb = node[i*2].deb;
node[i].fin = node[i*2+1].fin;
}
for(int i = 0; i < N; i++)
node[i].a = -INF, node[i].b = INF;
for(int i = 0; i < k; i++) {
if(op[i] == 1)
update(1, left[i], right[i]+1, height[i], INF);
else
update(1, left[i], right[i]+1, -INF, height[i]);
}
for(int i = 1; i < M; i++) {
applyOp(i*2, node[i].a, node[i].b);
applyOp(i*2+1, node[i].a, node[i].b);
}
for(int i = 0; i < n; i++)
finalHeight[i] = min(node[i+M].b, max(node[i+M].a, 0));
}
