#include "wall.h"
#include <bits/stdc++.h>
#ifdef GUDEB
#define D(x) cerr << #x << ": " << (x) << '\n';
#define ifdeb if(true)
#else
#define D(x) ;
#define ifdeb if(false)
#endif
#define all(x) begin(x), end(x)
using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;
int n;
int s;
int lbs[8000000];
int ubs[8000000];
void push(int x) {
if(x >= s) return;
for(int c : {2*x, 2*x+1}) {
lbs[c] = max(lbs[c], lbs[x]);
lbs[c] = min(lbs[c], ubs[x]);
ubs[c] = min(ubs[c], ubs[x]);
ubs[c] = max(ubs[c], lbs[x]);
}
ubs[x] = 100000;
lbs[x] = 0;
}
void walk(int l, int r, int op, int h, int u, int lu, int ru) {
D(l)
D(r)
D(u)
D(lu)
D(ru)
if(r <= lu || ru <= l) return;
if(l <= lu && ru <= r) {
if(op == 1) {
lbs[u] = max(lbs[u], h);
ubs[u] = max(ubs[u], lbs[u]);
} else {
ubs[u] = min(ubs[u], h);
lbs[u] = min(lbs[u], ubs[u]);
}
return;
}
push(u);
int mu = (lu+ru)/2;
walk(l, r, op, h, 2*u , lu, mu);
walk(l, r, op, h, 2*u+1, mu, ru);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
s = 1;
while(s < n) s *= 2;
for(int i = s-1; i > 0; --i) {
ubs[i] = 100000;
}
for(int i = 0; i < k; ++i) {
walk(left[i], right[i]+1, op[i], height[i], 1, 0, s);
}
for(int i = 1; i < s; ++i) {
push(i);
}
for(int i = 0; i < n; ++i) {
finalHeight[i] = lbs[s+i];
}
}
