#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct Info {
int add;
int del;
int press;
/**
ADD can't be more than DEL
ADD < DEL
*/
bool have;
};
int t[8000001];
Info tAdd[8000001];
void tr(Info &NEED, Info &gov) {
if (!gov.have)return;
if (!NEED.have){NEED = gov;return;}
if (gov.press != -1) {NEED = {-1, -1, gov.press, true};return;}
if (NEED.press != -1) {
if (gov.add != -1)NEED.press = max(NEED.press, gov.add);
if (gov.del != -1)NEED.press = min(NEED.press, gov.del);
return;
}
if (NEED.add == -1 && NEED.del != -1) {
if (gov.del != -1)NEED.del = min(NEED.del, gov.del);
if (gov.add != -1) {
if (NEED.del <= gov.add) {
NEED = {-1, -1, gov.add, true};
} else {
NEED.add = gov.add;
}
}
return;
}
if (NEED.add != -1 && NEED.del == -1) {
if (gov.add != -1)NEED.add = max(NEED.add, gov.add);
if (gov.del != -1) {
if (NEED.add >= gov.del) {
NEED = {-1, -1, gov.del, true};
} else {
NEED.del = gov.del;
}
}
return;
}
if (NEED.add != -1 && NEED.del != -1) {
/**
NEED.add < NEED.del <= gov.add < gov.del
gov.add < gov.del <= NEED.add < NEED.del
NEED.add <= gov.add < gov.del <= NEED.del
gov.add <= NEED.add < NEED.del <= gov.del
NEED.add <= gov.add < NEED.del <= gov.del
NEED.add < gov.add <= NEED.del < gov.del
gov.add <= NEED.add < gov.del <= NEED.del
gov.add < NEED.add <= gov.del < NEED.del
*/
if (gov.add != -1 && gov.del == -1) {
if (NEED.del <= gov.add) {
NEED = {-1, -1, gov.add, true};
} else {
NEED.add = max(NEED.add, gov.add);
}
} else if (gov.add == -1 && gov.del != -1) {
if (gov.del <= NEED.add) {
NEED = {-1, -1, gov.del, true};
} else {
NEED.del = min(NEED.del, gov.del);
}
} else {
if (NEED.del <= gov.add) {
NEED = {-1, -1, gov.add, true};
} else if (gov.del <= NEED.add) {
NEED = {-1, -1, gov.del, true};
} else {
NEED.add = max(NEED.add, gov.add);
NEED.del = min(NEED.del, gov.del);
}
}
return;
}
exit(1);
return;
}
void push(int v, int vl, int vr) {
if (!tAdd[v].have)return;
if (vl == vr) {
if (tAdd[v].press != -1) {
t[v] = tAdd[v].press;
} else {
if (tAdd[v].del != -1)t[v] = min(t[v], tAdd[v].del);
if (tAdd[v].add != -1)t[v] = max(t[v], tAdd[v].add);
}
} else {
tr(tAdd[2 * v], tAdd[v]);
tr(tAdd[2 * v + 1], tAdd[v]);
}
tAdd[v].add = -1;
tAdd[v].del = -1;
tAdd[v].press = -1;
tAdd[v].have = false;
}
void upd(int v, int vl, int vr, int l, int r, int val, int ty) {
push(v, vl, vr);
if (l <= vl && vr <= r) {
Info go;
if (ty == 1)go = {val, -1, -1, true};
if (ty == 2)go = {-1, val, -1, true};
tr(tAdd[v], go);
push(v, vl, vr);
return;
}
if (r < vl || vr < l)return;
int vm = (vl + vr) / 2;
upd(2 * v, vl, vm, l, r, val, ty);
upd(2 * v + 1, vm + 1, vr, l, r, val, ty);
}
int gt(int v, int vl, int vr, int pos) {
push(v, vl, vr);
if (vl == vr)return t[v];
int vm = (vl + vr) / 2;
if (pos <= vm)return gt(2 * v, vl, vm, pos);
return gt(2 * v + 1, vm + 1, vr, pos);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 1; i <= 4*n; i++) {
tAdd[i].add = -1;
tAdd[i].del = -1;
tAdd[i].press = -1;
tAdd[i].have = false;
}
for (int id = 0; id < k; id++) {
upd(1, 1, n, left[id] + 1, right[id] + 1, height[id], op[id]);
}
for (int i = 1; i <= n; i++)
finalHeight[i - 1] = gt(1, 1, n, i);
}
/**
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/
