/*input
*/
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
struct node {
int l, r;
int low;
int high;
node *left = nullptr;
node *right = nullptr;
node(int a, int b): l(a), r(b) {
low = 0;
high = 0;
if (l != r) {
left = new node(l, (l + r) / 2);
right = new node((l + r) / 2 + 1, r);
}
}
inline void push() {
if (l != r) {
for (auto && chil : {left, right}) {
chil->low = max(chil->low, low);
chil->low = min(chil->low, high);
chil->high = max(chil->high, low);
chil->high = min(chil->high, high);
}
}
}
inline void fix() {
if (l != r) {
for (auto && chil : {left, right}) {
low = min(chil->low, low);
high = max(chil->high, high);
}
}
}
void addLow(int a, int b, int w) {
push();
if (r < a or b < l) return;
else if (a <= l and r <= b) {
low = max(low, w);
high = max(high, low);
return;
} else {
left->addLow(a, b, w);
right->addLow(a, b, w);
}
fix();
}
void addHigh(int a, int b, int w) {
push();
if (r < a or b < l) return;
else if (a <= l and r <= b) {
high = min(high, w);
low = min(high, low);
return;
} else {
left->addHigh(a, b, w);
right->addHigh(a, b, w);
}
fix();
}
void finish(int final[]) {
push();
if (l == r) {
// printf("l = %d, r = %d, low = %d, high = %d\n", l, r, low, high);
final[l] = low;
} else {
left->finish(final);
right->finish(final);
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
node medis(0, n - 1);
for (int i = 0; i < k; ++i)
{
if (--op[i])
medis.addHigh(left[i], right[i], height[i]);
else
medis.addLow(left[i], right[i], height[i]);
}
medis.finish(finalHeight);
}
