#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define MAXI (int)1e5
struct segtree{
int size;
vector<int> tree;
vector<bool> marked;
void init(int n){
int x = 1;
while(x < n) x*=2;
size = x;
tree.assign(2*size,0);
marked.assign(2*size,0);
}
void pushMin(int v){
if(marked[v]){
tree[2*v+1] = min(tree[v],tree[2*v+1]);
tree[2*v+2] = min(tree[v],tree[2*v+2]);
marked[v] = false;
marked[2*v+1] = marked[2*v+2] = true;
}
}
void pushMax(int v){
if(marked[v]){
tree[2*v+1] = max(tree[v],tree[2*v+1]);
tree[2*v+2] = max(tree[v],tree[2*v+2]);
marked[v] = false;
marked[2*v+1] = marked[2*v+2] = true;
}
}
void maximize(int val,int l,int r,int x,int lx,int rx){
if(l > r) return;
if(l == lx && r == rx){
tree[x] = max(tree[x],val);
marked[x] = 1;
}else{
pushMax(x);
int mid = (lx+rx)/2;
maximize(val,l,r,2*x+1,lx,mid);
maximize(val,l,r,2*x+2,mid,rx);
}
}
void maximize(int val,int l,int r){
maximize(val,l,r,0,0,size);
}
void minimize(int val,int l,int r,int x,int lx,int rx){
if(l > r) return;
if(l == lx && r == rx){
tree[x] = min(tree[x],val);
marked[x] = 1;
}else{
pushMin(x);
int mid = (lx+rx)/2;
minimize(val,l,r,2*x+1,lx,mid);
minimize(val,l,r,2*x+2,mid,rx);
}
}
void minimize(int val,int l,int r){
minimize(val,l,r,0,0,size);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[],int finalHeight[]){
segtree s;
s.init(n);
for(int i = 0;i<k;i++){
if(op[i] == 1){
s.maximize(height[i],left[i],right[i]);
}else{
s.minimize(height[i],left[i],right[i]);
}
}
int ptr = s.size/2-1;
for(int i = 0;i<n;i++){
finalHeight[i] = s.tree[ptr++];
}
}
