#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
pair<int,int>tree[1<<22];
pair<int,int>merge(pair<int,int>x,pair<int,int>y){
pair<int,int>p={min(x.first,y.first),max(x.second,y.second)};
if(p.first<p.second){
if(x.second>y.first){
p.second=p.first;
}
else{
p.first=p.second;
}
}
return p;
}
void update(int k,int l,int r,int p,int q,pair<int,int>val){
if(q<l||r<p)return;
else if(p<=l&&r<=q){
tree[k]=merge(tree[k],val);
}
else{
tree[k+k]=merge(tree[k+k],tree[k]);
tree[k+k+1]=merge(tree[k+k+1],tree[k]);
tree[k]={0xE869120,0};
update(k+k,l,(l+r)/2,p,q,val);
update(k+k+1,(l+r)/2+1,r,p,q,val);
}
}
int calc(int x){
pair<int,int>a={0,0};
x+=(1<<21);
while(x){
a=merge(a,tree[x]);
x/=2;
}
return a.first;
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<(1<<22);i++){
tree[i]={0,0};
}
for(int i=0;i<K;i++){
if(op[i]==1){
update(1,0,(1<<21)-1,left[i],right[i],pair<int,int>{0xE869120,height[i]});
}
else{
update(1,0,(1<<21)-1,left[i],right[i],pair<int,int>{height[i],0});
}
}
for(int i=0;i<N;i++){
finalHeight[i]=calc(i);
}
}
