#include "wall.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Noeud {
int mini = 1e9, maxi = 0;
Noeud(int _mn = 1e9, int _mx = 0) {
mini = _mn;
maxi = _mx;
}
};
Noeud fusion(Noeud avant, Noeud apres) {
Noeud ret(min(avant.mini, apres.mini), max(avant.maxi, apres.maxi));
if (apres.mini < ret.maxi) {
ret.maxi = apres.mini;
}
if (apres.maxi > ret.mini) {
ret.mini = apres.maxi;
}
return ret;
}
struct segtree {
int taille = 1;
vector<Noeud> tree;
segtree(int _n) {
while(taille < _n) taille <<= 1;
tree.resize(taille*2);
}
void prop(int pos) {
if (pos < taille) {
tree[2*pos] = fusion(tree[2*pos], tree[pos]);
tree[2*pos+1] = fusion(tree[2*pos+1], tree[pos]);
tree[pos] = Noeud();
}
}
void modif(int lr, int rr, int l, int r, int pos, Noeud m) {
if (r <= lr || l >= rr) {
return;
}
if (l >= lr && r <= rr) {
tree[pos] = fusion(tree[pos], m);
return;
}
prop(pos);
int mid = (l+r)/2;
modif(lr, rr, l, mid, 2*pos, m);
modif(lr, rr, mid, r, 2*pos+1, m);
}
};
void buildWall(signed n, signed k, signed op[], signed left[], signed right[], signed height[], signed finalHeight[]){
segtree mur(n);
for (int i = 0; i < k; i++)
{
if (op[i] == 1) {
mur.modif(left[i], right[i]+1, 0, mur.taille, 1, {(int)1e9, height[i]});
}
else {
mur.modif(left[i], right[i]+1, 0, mur.taille, 1, {height[i], 0});
}
}
for (int i = 0; i < mur.taille; i++)
{
mur.prop(i);
}
for (int i = 0; i < n; i++)
{
Noeud actuel = mur.tree[mur.taille + i];
finalHeight[i] = actuel.maxi;
}
return;
}
