#include <bits/stdc++.h>
using namespace std;
#include "wall.h"
struct item {
int rem , fin;
};
struct Seg {
int siz;
vector<item> sum;
item nutral = {INT_MAX , 0};
item merge(item a , item b){
item ans;
ans.fin = max(a.fin , min(b.fin , a.rem));
ans.rem = min(a.rem , b.rem);
return ans;
}
void init(int n){
siz = 1;
while(siz < n)siz *= 2;
sum.assign(siz * 2 , nutral);
}
vector<int> v;
void set(int n , int x , int lx , int rx){
if(rx - lx == 1){
if(lx < n)v.push_back(sum[x].fin);
return;
}
sum[2 * x + 1] = merge(sum[x] , sum[2 * x + 1]);
sum[2 * x + 2] = merge(sum[x] , sum[2 * x + 2]);
sum[x] = nutral;
int m = (lx + rx)/2;
set(n , 2 * x + 1 , lx , m);
set(n , 2 * x + 2 , m , rx);
}
vector<int> setall(int n){
v.clear();
set(n , 0 , 0 , siz);
return v;
}
void range_set(int l, int r , int op , int h , int x , int lx , int rx){
if(rx <= l || lx >= r){
return;
}
if(lx >= l && rx <= r){
if(op == 2){
sum[x].fin = min(sum[x].fin , h);
sum[x].rem = min(sum[x].rem , h);
}
else sum[x].fin = max(sum[x].fin , h);
return;
}
sum[2 * x + 1] = merge(sum[x] , sum[2 * x + 1]);
sum[2 * x + 2] = merge(sum[x] , sum[2 * x + 2]);
sum[x] = nutral;
int m = (lx + rx)/2;
range_set(l , r , op , h , 2 * x + 1 , lx , m);
range_set(l ,r , op , h , 2 * x + 2 , m, rx);
}
void range_set(int l , int r , int op , int h){
range_set(l , r , op , h , 0 , 0 , siz);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int hei[], int finalHeight[]){
Seg st;
st.init(n);
for(int i = 0; i < k; i++){
st.range_set(left[i] , right[i]+1 , op[i] , hei[i]);
}
vector<int> v = st.setall(n);
for(int i = 0; i < n; i++)finalHeight[i] = v[i];
}
