#include <bits/stdc++.h>
#include "wall.h"
const int MAXN = 2000000;
const int MAXP = 2097152;
const int INF = 2e9;
int vst[2 * MAXP], vdr[2 * MAXP], vrez[MAXN];
//toate valorile din interval sunt >= vst[nod] si <= vdr[nod]
//vst si vdr sunt mereu valorile lazy
int minim(int a, int b) {
return a < b ? a : b;
}
int maxim(int a, int b) {
return a > b ? a : b;
}
void build(int nod, int st, int dr) {
int mid;
vst[nod] = 0;
vdr[nod] = INF;
if (st < dr) {
mid = (st + dr) / 2;
build(2 * nod, st, mid);
build(2 * nod + 1, mid + 1, dr);
}
}
void schimb(int nod, int val, int tip) {
if (tip == 1) {
vst[nod] = maxim(vst[nod], val);
vdr[nod] = maxim(vdr[nod], val);
} else {
vst[nod] = minim(vst[nod], val);
vdr[nod] = minim(vdr[nod], val);
}
}
void lazy(int nod) {
schimb(2 * nod, vst[nod], 1);
schimb(2 * nod, vdr[nod], 2);
schimb(2 * nod + 1, vst[nod], 1);
schimb(2 * nod + 1, vdr[nod], 2);
vst[nod] = 0;
vdr[nod] = INF;
}
void update(int nod, int st, int dr, int x, int y, int val, int tip) {
int mid;
if (x <= st && y >= dr) {
schimb(nod, val, tip);
} else {
lazy(nod);
mid = (st + dr) / 2;
if (x <= mid) {
update(2 * nod, st, mid, x, y, val, tip);
}
if (y > mid) {
update(2 * nod + 1, mid + 1, dr, x, y, val, tip);
}
}
}
void propag(int nod, int st, int dr) {
int mid;
if (st == dr) {
vrez[st - 1] = vst[nod];
} else {
lazy(nod);
mid = (st + dr) / 2;
propag(2 * nod, st, mid);
propag(2 * nod + 1, mid + 1, dr);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
//operatia de tip 1 face pe interval x = max(x, h)
//operatia de tip 2 face pe interval x = min(x, h)
//si tin valorile lazy de la fiecare interval din aint de la maximul si minimul posibil al valorilor din acel interval
int i;
build(1, 1, n);
for (i = 0; i < k; i++) {
update(1, 1, n, left[i] + 1, right[i] + 1, height[i], op[i]);
}
propag(1, 1, n);
for (i = 0; i < n; i++) {
finalHeight[i] = vrez[i];
}
}
