#include "wall.h"
const int MAX_N = 20000;
const int NINF = -1 * (1 << 30);
const int INF = (1<<30);
struct node {
int tmin = -1;
int tmax = -1;
int opmin = INF;
int opmax = NINF;
};
node segt[4*MAX_N+1];
void upd(int l, int r, int idx, int tl, int tr, int w, int h, int t){
if (l > tr || r < tl){
return;
}
if (l >= tl && r <= tr){
//mini
if (w == 1){
if (h <= segt[idx].opmin || segt[idx].tmin == -1){
segt[idx].opmin = h;
segt[idx].tmin = t;
}
if (h <= segt[idx].opmax || segt[idx].tmax == -1){
segt[idx].opmax = h;
segt[idx].tmax = t;
}
} else {
if (h >= segt[idx].opmax || segt[idx].tmin == -1){
segt[idx].opmax = h;
segt[idx].tmax = t;
}
if (h >= segt[idx].opmin || segt[idx].tmax == -1){
segt[idx].opmin = h;
segt[idx].tmin = t;
}
}
return;
}
int m = (l+r)/2;
upd(l,m,2*idx+1,tl,tr,w,h,t);
upd(m+1,r,2*idx+2,tl,tr,w,h,t);
return;
}
void solve(int l, int r, int idx, int finalHeight[], node a){
if (segt[idx].opmin <= a.opmax && segt[idx].tmin > a.tmax){
a.opmax = segt[idx].opmin;
a.tmax = segt[idx].tmin;
}
if (segt[idx].opmin <= a.opmin && segt[idx].tmin > a.tmin){
a.tmin = segt[idx].tmin;
a.opmin = segt[idx].opmin;
}
if (segt[idx].opmax >= a.opmax && segt[idx].tmax > a.tmax){
a.opmax = segt[idx].opmax;
a.tmax = segt[idx].tmax;
}
if (segt[idx].opmax >= a.opmin && segt[idx].tmax > a.tmin){
a.opmin = segt[idx].opmax;
a.tmin = segt[idx].tmax;
}
if (l == r){
/* if (a.opmin != a.opmax){
cout << "UHOHSPAGHETIIO " << l << ' ' << r << " " << idx << " " << a.opmin << " " << a.opmax << '\n';
}*/
if (a.opmin == INF && a.opmax == NINF){
finalHeight[l] = 0;
} else if (a.opmin == INF){
finalHeight[l] = a.opmax;
} else if (a.opmax == INF){
finalHeight[l] = a.opmin;
} else {
finalHeight[l] = a.opmin;
}
return;
}
int m = (l+r)/2;
solve(l,m,2*idx+1,finalHeight,a);
solve(m+1,r,2*idx+2,finalHeight,a);
return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int l,r,w,h,idx;
for (int i =0; i < k; i++){
w = op[i]-1;
h = height[i];
idx = i;
l = left[i];
r = right[i];
upd(0,n-1,0,l,r,w,h,idx);
}
node a;
solve(0,n-1,0,finalHeight,a);
return;
}
