#include "wall.h"
#include <algorithm>
#define N 2097152
#define INF 987654321
int seg[2*N];
int minh[2*N];
int maxh[2*N];
void updatelazy(int ind){
if(minh[ind]==-INF) return;
seg[ind]=std::max(seg[ind],minh[ind]);
seg[ind]=std::min(seg[ind],maxh[ind]);
if(ind<N){
if(maxh[2*ind]<minh[ind]) minh[2*ind]=maxh[2*ind]=minh[ind];
if(maxh[ind]<minh[2*ind]) minh[2*ind]=maxh[2*ind]=maxh[ind];
maxh[2*ind]=std::min(maxh[ind],maxh[2*ind]);
minh[2*ind]=std::max(minh[ind],minh[2*ind]);
if(maxh[2*ind+1]<minh[ind]) minh[2*ind+1]=maxh[2*ind+1]=minh[ind];
if(maxh[ind]<minh[2*ind+1]) minh[2*ind+1]=maxh[2*ind+1]=maxh[ind];
maxh[2*ind+1]=std::min(maxh[ind],maxh[2*ind+1]);
minh[2*ind+1]=std::max(minh[ind],minh[2*ind+1]);
}
minh[ind]=-INF;
maxh[ind]=INF;
return;
}
void set(int ind,int indleft,int indright,int minv,int maxv,int left,int right){
if(left<=indleft && indright <=right){
if(maxh[ind]<minv) maxh[ind]=minh[ind]=minv;
if(maxv<minh[ind]) minh[ind]=maxh[ind]=maxv;
maxh[ind]=std::min(maxh[ind],maxv);
minh[ind]=std::max(minh[ind],minv);
updatelazy(ind);
return;
}
updatelazy(ind);
if(indright<left || right < indleft) return;
if(ind<N){
set(2*ind,indleft,(indleft+indright)/2,minv,maxv,left,right);
set(2*ind+1,(indleft+indright)/2+1,indright,minv,maxv,left,right);
}
return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=1;i<2*N;i++) minh[i]=-INF,maxh[i]=INF;
for(int i=0;i<k;i++){
if(op[i]==2) set(1,0,N-1,0,height[i],left[i],right[i]);
else set(1,0,N-1,height[i],INF,left[i],right[i]);
}
for(int i=1;i<N+n;i++) updatelazy(i);
for(int i=0;i<n;i++) finalHeight[i]=seg[N+i];
return;
}
