#include "wall.h"
//OMG PINK FLOYD REFERANCE
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/codes/ioi14_d1/debug.h"
#else
#define debug(...) void(37)
#endif
template<typename T>
vector<T> inverse_fuck(T* a, int N) {
vector<T> res(N);
for (int i = 0; i < N; ++i) {
res[i] = a[i];
}
return res;
}
const int inf = int(1e6);
struct node {
int mx = 0, mn = inf;
int set = -1;
void push(node x) {
if (x.set != -1) {
set = x.set;
} else if (set != -1) {
set = max(set, x.mx);
set = min(set, x.mn);
} else {
if (x.mx >= mn) {
set = x.mx;
assert(x.mn > mx);
} else if (x.mn <= mx) {
set = x.mn;
} else {
mx = max(mx, x.mx);
mn = min(mn, x.mn);
}
}
}
};
#define def int mid = (l + r) >> 1, rv = (v + (mid - l) * 2)
struct SegTree {
vector<node> tree;
int n;
SegTree(int _n) : n(_n) {
tree.resize(n * 2 - 1);
}
void push_tags(int v, int rv) {
tree[v + 1].push(tree[v]);
tree[rv].push(tree[v]);
tree[v] = node{};
}
void modify(int v, int l, int r, int ll, int rr, bool op, int x) {
if (l >= ll && rr >= r) {
node add{};
(op ? add.mx : add.mn) = x;
tree[v].push(add);
return;
}
def;
push_tags(v, rv);
if (mid > ll) {
modify(v + 1, l, mid, ll, rr, op, x);
}
if (mid < rr) {
modify(rv, mid, r, ll, rr, op, x);
} //check closed - open intervals just in-case
}
void push(int v, int l, int r, vector<int>& res) {
debug(l, r, tree[v].mn, tree[v].mx);
if (l + 1 == r) {
res[l] = (tree[v].set == -1 ? tree[v].mx : tree[v].set);
return;
}
def;
push_tags(v, rv);
push(v + 1, l, mid, res);
push(rv, mid, r, res);
}
vector<int> get() {
vector<int> res(n);
push(0, 0, n, res);
return res;
}
void modify(int l, int r, bool op, int x) {
modify(0, 0, n, l, r + 1, op, x);
}
};
void buildWall(int n, int k, int fuck_op[], int fuck_left[], int fuck_right[], int fuck_height[], int fuck_finalHeight[]){
auto O = inverse_fuck(fuck_op, k);
auto L = inverse_fuck(fuck_left, k);
auto R = inverse_fuck(fuck_right, k);
auto H = inverse_fuck(fuck_height, k);
SegTree st(n);
for (int i = 0; i < k; ++i) {
debug(L[i], R[i], O[i] == 1, H[i]);
st.modify(L[i], R[i], O[i] == 1, H[i]);
}
auto res = st.get();
for (int i = 0; i < n; ++i) {
fuck_finalHeight[i] = res[i];
}
return;
}
