#include "wall.h"
#include <climits>
#include <algorithm>
#include <cassert>
#include <vector>
//clamps to [a,b]
struct Node{
int a,b;
Node():a(INT_MIN),b(INT_MAX){
}
Node(int a,int b):a(a),b(b){
assert(a<=b);
}
int eval(int x){
return std::max(a,std::min(b,x));
}
};
//apply l, then r
struct Node combine(struct Node l,struct Node r){
if(l.b<r.a) return Node(r.a,r.a);
if(l.a>r.b) return Node(r.b,r.b);
return Node(std::max(l.a,r.a),std::min(l.b,r.b));
}
struct Node st[1000005];
struct Node alt[500005];
std::vector<int> delta[2000005];
int K;
void pull(int i){
st[i]=combine(st[i<<1],st[i<<1|1]);
}
void update(int i){
for(i+=K;i>1;i>>=1){
pull(i>>1);
}
}
struct Node query(int a,int b){
struct Node lsum,rsum;
for(a+=K,b+=K;a<b;a>>=1,b>>=1){
if(a&1) lsum=combine(lsum,st[a++]);
if(b&1) rsum=combine(st[--b],rsum);
}
return combine(lsum,rsum);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
K=k;
for(int i=0;i<k;i++){
if(op[i]==1){
alt[i]=Node(height[i],INT_MAX);
}else{
alt[i]=Node(INT_MIN,height[i]);
}
delta[left[i]].push_back(i);
delta[right[i]+1].push_back(i);
}
for(int i=0;i<n;i++){
for(int x:delta[i]){
std::swap(st[x+K],alt[x]);
update(x);
}
finalHeight[i]=query(0,K).eval(0);
}
return;
}
