#include "wall.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct operation
{
int minb = -1e9, maxb = 1e9, fixed = -1;
int apply(int old)
{
if (fixed != -1) return fixed;
return min(maxb, max(minb, old));
}
};
operation merge(operation o1, operation o2) // o2 after o1
{
if (o2.fixed != -1)
{
return operation{(int)-1e9, (int)1e9, o2.fixed};
}
else if (o1.fixed != -1)
{
return operation{(int)-1e9, (int)1e9, min(o2.maxb, max(o2.minb, o1.fixed))};
}
operation res;
res.minb = max(o1.minb, o2.minb);
res.maxb = min(o1.maxb, o2.maxb);
if (res.maxb <= res.minb)
{
res.fixed = (res.minb == o2.minb ? o2.minb : o2.maxb);
res.minb = -1e9;
res.maxb = 1e9;
}
return res;
}
struct segtree
{
vector<int> table;
vector<operation> ops;
void apply(int pos, operation op)
{
ops[pos] = merge(ops[pos], op);
table[pos] = op.apply(table[pos]);
}
void propagate(int pos)
{
apply(2*pos + 1, ops[pos]);
apply(2*pos + 2, ops[pos]);
ops[pos] = operation();
}
void update(int ql, int qr, operation op, int l, int r, int pos)
{
if (ql <= l && r <= qr)
{
apply(pos, op);
return;
}
if (r < ql || qr < l) return;
propagate(pos);
update(ql, qr, op, l, (l + r)/2, 2*pos + 1);
update(ql, qr, op, (l + r)/2 + 1, r, 2*pos + 2);
}
int query(int k, int l, int r, int pos)
{
if (l == r) return table[pos];
propagate(pos);
if (k <= (l + r)/2) return query(k, l, (l + r)/2, 2*pos + 1);
else return query(k, (l + r)/2 + 1, r, 2*pos + 2);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
segtree st;
st.ops.resize(4*n);
st.table.resize(4*n);
for (int i = 0; i < k; i++)
{
operation nop;
if (op[i] == 1) nop.minb = height[i];
else nop.maxb = height[i];
st.update(left[i], right[i], nop, 0, n - 1, 0);
}
for (int i = 0; i < n; i++)
{
finalHeight[i] = st.query(i, 0, n - 1, 0);
}
}
