#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct inter {
int deb, fin;
int mid() {
return (deb+fin)/2;
}
inter left() {
return {deb, mid()};
}
inter right() {
return {mid()+1, fin};
}
bool contain(inter other) {
return (deb <= other.deb && other.fin <= fin);
}
bool intersect(inter other) {
return !(other.fin < deb || other.deb > fin);
}
inter intersection(inter other) {
if(intersect(other)) {
return {max(deb, other.deb), min(fin, other.fin)};
}
if(other.fin < deb) {
return {other.fin, other.fin};
}
return {other.deb, other.deb};
}
};
struct SegTree {
int n = 1;
inter zero = {0, int(1e9)};
vector<inter> tree;
void init(int _n) {
while(n < _n) {
n *= 2;
}
tree.resize(2*n, zero);
}
void push(int pos) {
if(pos < n) {
tree[2*pos] = tree[2*pos].intersection(tree[pos]);
tree[2*pos+1] = tree[2*pos+1].intersection(tree[pos]);
tree[pos] = zero;
}
}
void fullPush() {
for(int loop = 1; loop < n; ++loop) {
push(loop);
}
}
void modif(inter value, inter zoneModif, int pos, inter nodeInter) {
push(pos);
if(zoneModif.contain(nodeInter)) {
tree[pos] = tree[pos].intersection(value);
}
else {
if(zoneModif.intersect(nodeInter.left())) {
modif(value, zoneModif, pos*2, nodeInter.left());
}
if(zoneModif.intersect(nodeInter.right())) {
modif(value, zoneModif, pos*2+1, nodeInter.right());
}
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegTree tree;
tree.init(n);
inter mod[k], modInter[k];
for(int loop = 0; loop < k; ++loop) {
if(op[loop] == 1) {
mod[loop] = {height[loop], int(1e9)};
}
else {
mod[loop] = {0, height[loop]};
}
modInter[loop] = {left[loop], right[loop]};
}
for(int loop = 0; loop < k; ++loop) {
tree.modif(mod[loop], modInter[loop], 1, {0, tree.n - 1});
}
tree.fullPush();
for(int loop = 0; loop < n; ++loop) {
finalHeight[loop] = tree.tree[loop+tree.n].deb;
}
}
