#include "wall.h"
#ifdef ALE
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define lo first
#define hi second
const int nax=2e6+6;
const int inf=INT_MAX;
pair<int,int> rt[4*nax];
void merge(pair<int,int> a, pair<int,int>& b){
int oldhi=b.hi;
b.lo=max(a.lo,b.lo);
b.hi=min(a.hi,b.hi);
if(oldhi<a.lo)b.hi=b.lo;
else if(a.hi<b.lo)b.lo=b.hi;
}
void pre(int k, int x, int y){
if(x!=y){
merge(rt[k],rt[2*k]);
merge(rt[k],rt[2*k+1]);
rt[k]={0,inf};
}
}
void update(int k, int a, int b, int x, int y, int mval,int Mval){
pre(k,x,y);
if(x>b||y<a)return;
if(x>=a&&y<=b){
merge({mval,Mval},rt[k]);
return;
}
int m=(x+y)/2;
update(2*k,a,b,x,m,mval,Mval);
update(2*k+1,a,b,m+1,y,mval,Mval);
}
void solve(int k, int x, int y, int* f){
pre(k,x,y);
if(x>y)return;
if(x==y){
f[x]=rt[k].lo;
return;
}
int m=(x+y)/2;
solve(2*k,x,m,f);
solve(2*k+1,m+1,y,f);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<4*nax;i++)rt[k]={0,inf};
for(int i=0;i<k;i++){
if(op[i]==1)update(1,left[i],right[i],0,n-1,height[i],inf);
else update(1,left[i],right[i],0,n-1,0,height[i]);
}
solve(1,0,n-1,finalHeight);
}
