#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<21);
const int INF=1e9;
int tl[N+N], tr[N+N];
void prop(int v){
if(v>=N)return;
int l=v+v, r=l+1;
tl[l]=min(max(tl[l], tl[v]), tr[v]);
tl[r]=min(max(tl[r], tl[v]), tr[v]);
tr[l]=max(min(tr[l], tr[v]), tl[v]);
tr[r]=max(min(tr[r], tr[v]), tl[v]);
tl[v]=-INF;
tr[v]=INF;
}
void upd1(int v, int L, int R, int l, int r, int c){
if(L==l && r==R){
tr[v]=min(tr[v], c);
tl[v]=min(tl[v], c);
return;
}
prop(v);
int M=(L+R)>>1;
if(l<=M)upd1(2*v, L, M, l, min(r, M), c);
if(r>M)upd1(2*v+1, M+1, R, max(l, M+1), r, c);
return;
}
void upd2(int v, int L, int R, int l, int r, int c){
if(L==l && r==R){
tr[v]=max(tr[v], c);
tl[v]=max(tl[v], c);
return;
}
prop(v);
int M=(L+R)>>1;
if(l<=M)upd2(2*v, L, M, l, min(r, M), c);
if(r>M)upd2(2*v+1, M+1, R, max(l, M+1), r, c);
return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0; i<N; i++){
tr[i]=INF;
tl[i]=-INF;
}
for(int i=0; i<k; i++){
if(op[i]==1)upd2(1, 0, N-1, left[i], right[i], height[i]);
else upd1(1, 0, N-1, left[i], right[i], height[i]);
}
for(int i=1; i<N; i++){
prop(i);
}
for(int i=0; i<n; i++){
finalHeight[i]=tl[i+N];
}
return;
}
