#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int base = (1 << 21);
int minim[base*2];
int maxim[base*2];
int x, a, b;
bool cz;
void zrzuta(int v, int s){
if(minim[v] > minim[s]){
minim[s] = minim[v];
if(maxim[v] < maxim[s]){
maxim[s] = maxim[v];
}
else{
maxim[s] = max(maxim[s], minim[s]);
}
}
else{
if(maxim[v] < maxim[s]){
maxim[s] = maxim[v];
minim[s] = min(minim[s], maxim[s]);
}
}
}
void zmiana(int v, int l, int p){
if(a <= l && p <= b){
if(cz){
minim[v] = max(minim[v], x);
maxim[v] = max(maxim[v], x);
}
else{
maxim[v] = min(maxim[v], x);
minim[v] = min(minim[v], x);
}
return;
}
if(a > p || b < l){
return;
}
zrzuta(v, v*2);
zrzuta(v, v*2 + 1);
minim[v] = -100005;
maxim[v] = 100005;
zmiana(v*2, l, (l + p)/2);
zmiana(v*2 + 1, (l + p)/2 + 1, p);
}
void buildWall(int n, int k, int q[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 1; i < base*2; i++){
minim[i] = -100005;
maxim[i] = 100005;
}
for(int i = 0; i < k; i++){
a = left[i];
b = right[i];
x = height[i];
if(q[i] == 1){ // dodanie
cz = 1;
}
else{
cz = 0;
}
zmiana(1, 0, base - 1);
}
for(int i = 1; i < base; i++){
zrzuta(i, i*2);
zrzuta(i, i*2 + 1);
}
for(int i = 0; i < n; i++){
finalHeight[i] = min(max(0, minim[i + base]), maxim[i + base]);
}
}
