#include "wall.h"
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi; typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;
struct NODE{
int l, r; pi val;
NODE *lp, *rp;
NODE(int a, int b) : l(a), r(b), val(pi(0, 0)), lp(NULL), rp(NULL) {
if(a == b) return;
int m = (a+b) >> 1;
lp = new NODE(a, m);
rp = new NODE(m+1, b);
}
void lazy() {
if(lp) {
lp->val.one = max(lp->val.one, val.one);
lp->val.two = max(lp->val.two, val.one);
lp->val.one = min(lp->val.one, val.two);
lp->val.two = min(lp->val.two, val.two);
rp->val.one = max(rp->val.one, val.one);
rp->val.two = max(rp->val.two, val.one);
rp->val.one = min(rp->val.one, val.two);
rp->val.two = min(rp->val.two, val.two);
}
}
void update(int a, int b, pi v) {
if(b < l || r < a) return;
lazy();
if(a <= l && r <= b) {
if(v.one == -INF) {
val.one = min(val.one, v.two);
val.two = min(val.two, v.two);
}else if(v.two == INF) {
val.one = max(val.one, v.one);
val.two = max(val.two, v.one);
}
return;
}
lp->update(a, b, v);
rp->update(a, b, v);
val = pi(min(lp->val.one, rp->val.one), max(lp->val.two, rp->val.two));
}
int getV(int v) {
if(v < l || r < v) return -1;
if(l == r) return val.one;
lazy();
int lv = lp->getV(v);
int rv = rp->getV(v);
return max(lv, rv);
}
};
int N, Q;
void buildWall(int n, int k, int opp[], int ll[], int rr[], int hh[], int fh[]){
N = n; Q = k;
NODE *root = new NODE(0, N-1);
for(int q=0; q<Q; q++) {
// printf("%d start\n", q);
int o = opp[q], l = ll[q], r = rr[q], h = hh[q];
pi val = pi(-INF, +INF);
if(o == 1) val.one = h; else val.two = h;
root->update(l, r, val);
}
for(int i=0; i<N; i++) fh[i] = root->getV(i);
return;
}
