#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
using ii = pair<int, int>;
const int inf = 1e9;
const ii EMPTY = {-inf, inf};
ii merge(ii first, ii second) {
if(first.X > second.Y)
return {second.Y, second.Y};
if(first.Y < second.X)
return {second.X, second.X};
return {max(first.X, second.X), min(first.Y, second.Y)};
}
int doop(int x, ii op) {
return min(max(x, op.X), op.Y);
}
struct SegmentTree {
int lv;
vector<ii> lazy;
void init(int n) {
lv = 2;
while(lv < n)
lv *= 2;
lazy.resize(2 * lv + 2, EMPTY);
}
void push(int w, int l, int r) {
if(l != r) {
lazy[2 * w] = merge(lazy[2 * w], lazy[w]);
lazy[2 * w + 1] = merge(lazy[2 * w + 1], lazy[w]);
lazy[w] = EMPTY;
}
}
void insert(int a, int b, int w, int l, int r, ii op) {
push(w, l, r);
if(l > r || l > b || r < a)
return ;
if(a <= l && r <= b) {
lazy[w] = merge(lazy[w], op);
push(w, l, r);
return ;
}
insert(a, b, 2 * w, l, (l + r) / 2, op);
insert(a, b, 2 * w + 1, (l + r) / 2 + 1, r, op);
}
void insert(int a, int b, ii op) {
insert(a, b, 1, 0, lv - 1, op);
}
void push_all(int w, int l, int r) {
push(w, l, r);
if(l != r) {
push_all(2 * w, l, (l + r) / 2);
push_all(2 * w + 1, (l + r) / 2 + 1, r);
}
}
vector<int> calc() {
vector<int> res;
res.resize(lv);
push_all(1, 0, lv - 1);
//~ for(int i = 0 ; i < 2 * lv ; i++)
//~ cout << i << " " << lazy[i].X << " " << lazy[i].Y << endl;
//~ cout << endl;
for(int i = 0 ; i < lv ; i++)
res[i] = lazy[lv + i].X;
return res;
}
};
SegmentTree ST;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
ST.init(n);
for(int i = 0 ; i < k ; i++) {
if(op[i] == 1)
ST.insert(left[i], right[i], {height[i], inf});
else
ST.insert(left[i], right[i], {-inf, height[i]});
//~ for(int i = 0 ; i < 2 * ST.lv ; i++)
//~ cout << i << " " << ST.lazy[i].X << " " << ST.lazy[i].Y << endl;
//~ cout << endl;
}
vector<int> res = ST.calc();
for(int i = 0 ; i < n ; i++)
finalHeight[i] = max(0, res[i]);
}
