#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
int n;
int level,zereg[30];
vector<int> add[30], rem[30];
int l,r;
void build() {
zereg[0] = 1;
for(int i = 0; i < 30; i ++) {
if(zereg[i] >= n) {
level = i;
break;
}
zereg[i + 1] = zereg[i] * 2;
}
for(int i = 0; i <= level; i ++) {
for(int j = 0; j < zereg[i]; j ++) {
add[i].pb(-1);
rem[i].pb(-1);
}
}
}
void propogate(int k, int x) {
if(rem[k][x] != -1) {
if(rem[k + 1][x * 2] != -1) rem[k + 1][x * 2] = min(rem[k + 1][x * 2], rem[k][x]);
else rem[k + 1][x * 2] = rem[k][x];
if(add[k + 1][x * 2] > rem[k][x]) add[k + 1][x * 2] = rem[k][x];
//
if(rem[k + 1][x * 2 + 1] != -1) rem[k + 1][x * 2 + 1] = min(rem[k + 1][x * 2 + 1], rem[k][x]);
else rem[k + 1][x * 2 + 1] = rem[k][x];
if(add[k + 1][x * 2 + 1] > rem[k][x]) add[k + 1][x * 2 + 1] = rem[k][x];
rem[k][x] = -1;
}
add[k + 1][x * 2] = max(add[k + 1][x * 2], add[k][x]);
add[k + 1][x * 2 + 1] = max(add[k + 1][x * 2 + 1], add[k][x]);
add[k][x] = -1;
}
int go(int pos) {
int ret = 0;
for(int i = level; i >= 0; i --) {
if(rem[i][pos] != -1) if(ret > rem[i][pos]) ret = rem[i][pos];
ret = max(ret, add[i][pos]);
pos /= 2;
}
return ret;
}
void dfs(int k, int x, int type, int val) {
int y = zereg[level - k] * x;
int z = zereg[level - k] * (x + 1) - 1;
if(l <= y && z <= r) {
if(type == 1) { // adding phase
add[k][x] = max(add[k][x], val);
}
else {
if(rem[k][x] == -1) rem[k][x] = val;
else rem[k][x] = min(rem[k][x], val);
if(add[k][x] > val) add[k][x] = val;
}
return;
}
if(z < l || y > r || k == level) return;
propogate(k,x);
dfs(k + 1, x * 2, type, val);
dfs(k + 1, x * 2 + 1, type, val);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
build();
for(int i = 0; i < k; i ++) {
l = left[i];
r = right[i];
dfs(0,0,op[i],height[i]);
}
for(int i = 0; i < N; i ++) {
finalHeight[i] = go(i);
}
return;
}
