| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1098037 | orcslop | Wall (IOI14_wall) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }
bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }
const ll inf = 1e18;
struct Data {
ll mn = 0, mx = inf;
};
/**
* T = tree node type, which will be long long
* We use the Query struct to manage updates.
*/
template <class T> class LazySegtree {
private:
const int sz;
vector<Data> tree; // tree[i] = sum of this node's range
vector<Data> lazy; // lazy[i] = lazy update for the range
/** @return result of joining two tree nodes together */
/** applies lazy update to t[v], places update at lz[v] */
void apply(int v, const Data &x) {
ckmax(tree[v].mn, x.mn);
ckmax(tree[v].mx, tree[v].mn);
ckmin(tree[v].mx, x.mx);
ckmin(tree[v].mn, tree[v].mx);
}
/** pushes down lazy update to children of v */
void push_down(int v) {
apply(2 * v, tree[v]);
apply(2 * v + 1, tree[v]);
tree[v] = Data();
}
void range_update(int v, int l, int r, int ql, int qr, const Data &x) {
if (qr < l || ql > r) { return; }
if (ql <= l && r <= qr) {
apply(v, x);
} else {
push_down(v);
int m = (l + r) / 2;
range_update(2 * v, l, m, ql, qr, x);
range_update(2 * v + 1, m + 1, r, ql, qr, x);
}
}
Data get(int v, int pos, int l, int r) {
if (l == r) { return tree[v]; }
push_down(v);
int m = (l + r) / 2;
if(pos <= m) return get(2 * v, pos, l, m);
else return get(2 * v + 1, pos, m + 1, r);
}
public:
LazySegtree(int n) : sz(n), tree(4 * sz), lazy(4 * sz) {
}
/** updates [ql, qr] with the update x */
void range_update(int ql, int qr, const Data &x) {
range_update(1, 0, sz - 1, ql, qr, x);
}
/** sum of array values on [ql, qr] */
Data get(int pos) { return get(1, pos, 0, sz - 1); }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int final_height[]) {
LazySegtree st(n);
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
st.update(left[i], right[i], {height[i], inf});
} else {
st.update(left[i], right[i], {0, height[i]});
}
}
for (int i = 0; i < n; i++) {
Data c = st.get(i);
if(c.mn <= height[i] && height[i] <= c.mx){
final_height[i] = height[i];
}
else final_height[i] = c.mn;
}
}