#include "wall.h"
#include <bits/stdc++.h>
#define INF 1e+9
using namespace std;
typedef pair<int,int> P;
P dat[1050000];
int seg = 1;
P add(P p1,P p2){
int a = p1.first,b = p1.second,c = p2.first,d = p2.second;
return P(min(a,max(c,d)),min(max(b,d),max(c,d)));
}
int f(int x,P p){
return max(min(x,p.first),p.second);
}
void update(int i,P x){
i += seg - 1;
dat[i] = x;
while(i){
i = (i - 1) / 2;
dat[i] = add(dat[i * 2 + 1],dat[i * 2 + 2]);
}
}
void buildWall(int n, int k, int op[], int l[], int r[], int height[], int finalHeight[]){
while(seg < k) seg *= 2;
for(int i = 0;i < seg * 2 - 1;i++) dat[i] = P(INF,0);
vector<int> on[2000010],off[2000010];
for(int i = 0;i < k;i++){
on[l[i]].push_back(i);
off[r[i]].push_back(i);
}
for(int i = 0;i < n;i++){
for(int v : on[i]){
if(op[v] == 1) update(v,P(INF,height[v]));
else update(v,P(height[v],0));
}
finalHeight[i] = f(0,dat[0]);
for(int v : off[i]) update(v,P(INF,0));
}
}
