#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
#include "wall.h"
const int MX = 1e5 + 5;
pair<int, int> merge(pair<int, int> &a, pair<int, int> &b){
if(min(a.second, b.second) < max(a.first, b.first)){ // kesisme yok
if(b.first > a.second) return {b.first, b.first};
else return {b.second, b.second};
}
else{
return {max(a.first, b.first), min(a.second, b.second)};
}
}
struct SEGT{
vector<pair<int, int> > tree;
void init(int n){
tree.assign(4*n, {0, MX});
}
void update(int ind, int l, int r, int pos, pair<int, int> val){
if(l == r){
tree[ind] = val;
}
else{
int m = (l + r)/2;
if(pos <= m) update(ind*2, l, m, pos, val);
else update(ind*2+1, m+1, r, pos, val);
tree[ind] = merge(tree[ind*2], tree[ind*2+1]);
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
vector<array<int, 4> > updates[n+1];
for(int i = 0; i < k; i++){
updates[left[i]].pb({i+1, height[i], op[i], 1});
updates[right[i] + 1].pb({i+1, height[i], op[i], -1});
}
SEGT seg;
seg.init(k);
for(int i = 0; i < n; i++){
for(auto itr: updates[i]){
pair<int, int> val = {0, MX};
if(itr[3] == -1){
seg.update(1, 1, k, itr[0], val);
}
else{
if(itr[2] == 1) val = {itr[1], MX};
else val = {0, itr[1]};
seg.update(1, 1, k, itr[0], val);
}
}
finalHeight[i] = seg.tree[1].first;
}
return;
}
