#include"wall.h"
#include<iostream>
using namespace std;
const int TREE_SIZE=1<<21;
#define upper first
#define lower second
pair<int,int>tree[2*TREE_SIZE];
bool lazy[2*TREE_SIZE];
void update(int node){
if(node>=TREE_SIZE)
return;
if(lazy[node]){
tree[2*node].upper=min(tree[2*node].upper,tree[node].upper);
tree[2*node].upper=max(tree[2*node].upper,tree[node].lower);
tree[2*node].lower=min(tree[2*node].lower,tree[node].upper);
tree[2*node].lower=max(tree[2*node].lower,tree[node].lower);
tree[2*node+1].upper=min(tree[2*node+1].upper,tree[node].upper);
tree[2*node+1].upper=max(tree[2*node+1].upper,tree[node].lower);
tree[2*node+1].lower=min(tree[2*node+1].lower,tree[node].upper);
tree[2*node+1].lower=max(tree[2*node+1].lower,tree[node].lower);
lazy[2*node]=true;
lazy[2*node+1]=true;
lazy[node]=false;
}
}
void lh_bound(int node,int l,int r,int rl,int rr,pair<int,int>bound){
update(node);
if(r<=rl||rr<=l)
return;
if(l<=rl&&rr<=r){
tree[node].lower=max(tree[node].lower,bound.lower);
tree[node].lower=min(tree[node].lower,bound.upper);
tree[node].upper=max(tree[node].upper,bound.lower);
tree[node].upper=min(tree[node].upper,bound.upper);
lazy[node]=true;
return;
}
int mid=(rl+rr)/2;
lh_bound(2*node,l,r,rl,mid,bound);
lh_bound(2*node+1,l,r,mid,rr,bound);
tree[node].lower=min(tree[2*node].lower,tree[2*node+1].lower);
tree[node].upper=max(tree[2*node].upper,tree[2*node+1].upper);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
for(int i=0;i<k;i++){
if(op[i]==1){
// adding phase
pair<int,int>bound;
bound.lower=height[i];
bound.upper=1000000000;
lh_bound(1,left[i],right[i]+1,0,TREE_SIZE,bound);
}else{
// removing phase
pair<int,int>bound;
bound.lower=-1000000000;
bound.upper=height[i];
lh_bound(1,left[i],right[i]+1,0,TREE_SIZE,bound);
}
}
for(int i=1;i<2*TREE_SIZE;i++)
update(i);
for(int i=0;i<n;i++)
finalHeight[i]=tree[TREE_SIZE+i].lower;
}
