#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
/*
minA = min(min1, min2)
minA = max(minA, max2)
maxA = max(max1, max2)
maxA = min(maxA, min2)
*/
const int mxN = (int)4e7+5;
vector<int>mn(mxN, INT_MAX);
vector<int>mx(mxN, INT_MIN);
int l,r;
int MX, MN;
void reset(int p) {
mn[p] = INT_MAX;
mx[p] = INT_MIN;
}
void push(int mn_, int mx_, int p) {
mn[p] = min(mn[p], mn_);
mn[p] = max(mn[p], mx_);
mx[p] = max(mx[p], mx_);
mx[p] = min(mx[p], mn_);
}
void update(int i, int j, int p) {
if(i > r || j < l)
return;
if(i >= l && j <= r) {
mn[p] = min(mn[p], MN);
mn[p] = max(mn[p], MX);
mx[p] = max(mx[p], MX);
mx[p] = min(mx[p], MN);
return;
}
int mid = (i+j)/2;
push(mn[p], mx[p], 2*p);
push(mn[p], mx[p], 2*p+1);
reset(p);
update(i, mid, 2*p);
update(mid+1, j, 2*p+1);
}
int query(int i, int j, int p) {
if(i >= l && j <= r) {
return max(0, mx[p]);
}
int mid = (i+j)/2;
push(mn[p], mx[p], 2*p);
push(mn[p], mx[p], 2*p+1);
reset(p);
if(l <= mid)
return query(i, mid, 2*p);
return query(mid+1, j, 2*p+1);
}
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) {
MX = height[i];
MN = INT_MAX;
l = left[i];
r = right[i];
update(0, n-1, 1);
} else {
MX = INT_MIN;
MN = height[i];
l = left[i];
r = right[i];
update(0, n-1, 1);
}
}
for(int i = 0 ; i < n ; i++) {
l = i, r = i;
finalHeight[i] = query(0, n-1, 1);
}
}
