| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1287541 | harryleee | Wall (IOI14_wall) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
void buildWall(int n, int q, vector<int> t, vector<int> left, vector<int> right, vector<int> h, vector<int> a)
{
struct SEGMENT_TREE{
struct node{
int lo, hi;
bool inc;
inline node(){
lo = -1;
hi = 1e9;
inc = false;
}
}; vector<node> st;
inline SEGMENT_TREE(int n){
st.resize(4 * n);
}
inline void update_node(int ind, int h, int t, bool b){
st[ind].inc |= b;
if (t == 1){
st[ind].lo = max(st[ind].lo, h);
if (st[ind].lo > st[ind].hi) st[ind].hi = 1e9;
}
else{
st[ind].hi = min(st[ind].hi, h);
if (st[ind].hi < st[ind].lo) st[ind].lo = -1;
}
return;
}
inline void update(int ind, int l, int r, int lb, int rb, int h, int t){
if (l >= lb && r <= rb){
update_node(ind, h, t, (t == 1));
return;
}
if (st[ind].lo != -1)
update_node(ind << 1, st[ind].lo, 1, true), update_node(ind << 1 | 1, st[ind].lo, 1, true);
if (st[ind].hi != -1)
update_node(ind << 1, st[ind].hi, 2, st[ind].inc), update_node(ind << 1 | 1, st[ind].hi, 2, st[ind].inc);
st[ind] = node();
int mid = (l + r) >> 1;
if (mid >= lb) update(ind << 1, l, mid, lb, rb, h, t);
if (mid < rb) update(ind << 1 | 1, mid + 1, r, lb, rb, h, t);
return;
}
inline void get(int ind, int l, int r, vector<int>& a){
if (l == r){
if (a[l] < st[ind].lo) a[l] = st[ind].lo;
else if (a[l] > st[ind].hi) a[l] = st[ind].hi;
if (st[ind].lo == -1 && st[ind].hi != 1e9 && st[ind].inc) a[l] = st[ind].hi;
return;
}
if (st[ind].lo != -1)
update_node(ind << 1, st[ind].lo, 1, true), update_node(ind << 1 | 1, st[ind].lo, 1, true);
if (st[ind].hi != -1)
update_node(ind << 1, st[ind].hi, 2, st[ind].inc), update_node(ind << 1 | 1, st[ind].hi, 2, st[ind].inc);
st[ind] = node();
int mid = (l + r) >> 1;
get(ind << 1, l, mid, a);
get(ind << 1 | 1, mid + 1, r, a);
}
} seg(n);
for (int i = 0; i < q; ++i)
seg.update(1, 0, n - 1, left[i], right[i], h[i], t[i]);
seg.get(1, 0, n - 1, a);
}