#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
struct Segment{
inline int left(int i){return (i*2)+1;}
inline int right(int i){return (i+1)*2;}
vector<int> v;
vector<int> maxi;
vector<int> mini;
int S;
Segment(int N){
S = (1<<(int)ceil(log2(N)+1))-1;
v.resize(S, 0);
mini.resize(S, INF);
maxi.resize(S, -INF);
}
void check(int pos){
if(mini[pos] == -INF) return; //mai aggiornato
v[pos] = max(mini[pos], v[pos]);
v[pos] = min(maxi[pos], v[pos]);
if(pos < S/2){
if(maxi[left(pos)] < mini[pos]) mini[left(pos)] = maxi[left(pos)] = mini[pos];
if(maxi[pos] < mini[left(pos)]) mini[left(pos)] = maxi[left(pos)] = maxi[pos];
maxi[left(pos)] = min(maxi[pos], maxi[left(pos)]);
mini[left(pos)] = max(mini[pos], mini[left(pos)]);
if(maxi[right(pos)] < mini[pos]) mini[right(pos)] = maxi[right(pos)] = mini[pos];
if(maxi[pos] < mini[right(pos)]) mini[right(pos)] = maxi[right(pos)] = maxi[pos];
maxi[right(pos)] = min(maxi[pos], maxi[right(pos)]);
mini[right(pos)] = max(mini[pos], mini[right(pos)]);
}
mini[pos] = -INF;
maxi[pos] = INF;
}
void update(int pos, int a, int b, int l, int r, int mm, int MM){
if(a > r || b < l)
return;
check(pos);
if(a >= l && b <= r){
if(maxi[pos] < mm) maxi[pos] = mini[pos] = mm;
if(mm < mini[pos]) maxi[pos] = mini[pos] = MM;
maxi[pos] = min(maxi[pos], MM);
mini[pos] = max(mini[pos], mm);
check(pos);
return;
}
int mid = (a+b)/2;
update(left(pos), a, mid, l, r, mm, MM);
update(right(pos), mid+1, b, l, r, mm, MM);
}
void updateAll(){
for(int i=0; i<S; i++)
check(i);
}
int getAt(int i){
return v[S/2+i];
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
Segment st(n);
for(int i=0; i<k; i++){
if(op[i] == 1)
st.update(0, 0, st.S/2, left[i], right[i], height[i], INF);
else
st.update(0, 0, st.S/2, left[i], right[i], 0, height[i]);
}
st.updateAll();
for(int i=0; i<n; i++)
finalHeight[i] = st.getAt(i) == -INF ? 0 : st.getAt(i);
}
