#include "wall.h"
#include <iostream>
typedef int ll;
using namespace std;
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
ll lazy[4194304][2];
ll N = 2097152;
ll ans[2097152];
void prop(ll pos, ll mini, ll maxi){
if (maxi>= lazy[pos][0]){
lazy[pos][0] = maxi;
lazy[pos][1] = maxi;
}else{
lazy[pos][1] = max(maxi, lazy[pos][1]);
}
if (mini<= lazy[pos][1]){
lazy[pos][0] = mini;
lazy[pos][1] = mini;
}else{
lazy[pos][0] = min(mini, lazy[pos][0]);
}
}
void update(ll a, ll b, ll op, ll val, ll k=1, ll x=0, ll y=N-1){
if (b<x || a>y) return;
if (a<=x && y<=b){
if(op){
if (val >= lazy[k][0]){
lazy[k][0] = val;
lazy[k][1] = val;
}else{
lazy[k][1] = max(lazy[k][1],val);
}
}else{
if (val <= lazy[k][1]){
lazy[k][0] = val;
lazy[k][1] = val;
}else{
lazy[k][0] = min(lazy[k][0],val);
}
}
return;
}
prop(k*2,lazy[k][0],lazy[k][1]);
prop(k*2+1,lazy[k][0],lazy[k][1]);
lazy[k][0] = 100001;
lazy[k][1] = -1;
ll d = (x+y)/2;
update(a,b,op,val,2*k,x,d);
update(a,b,op,val,2*k+1,d+1,y);
return;
}
void propagate(){
FOR(i,1,N){
prop(i*2, lazy[i][0],lazy[i][1]);
prop(i*2+1, lazy[i][0],lazy[i][1]);
}
FOR(i,N,2*N){
ans[i-N] = (max(min(0,lazy[i][0]), lazy[i][1]));
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
FOR(i,0,4194304){
lazy[i][0] = 100001;
lazy[i][1] = -1;
}
FOR(i,0,k){
if (op[i]==2) op[i] = 0;
update(left[i], right[i], op[i], height[i]);
}
propagate();
FOR(i,0,n){
finalHeight[i] = ans[i];
}
}
