| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 484715 | WeissBlume | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"wall.h"
#include<cstdio>
#include<queue>
#include<memory>
#include<algorithm>
#define x first
#define y second
using namespace std;
using ii = pair<int, int>;
int read(int x = 0) { return scanf("%d", &x), x; }
template<class node_t>
struct LazySegmentTree {
using T = typename node_t::val_t;
using U = typename node_t::upd_t;
unique_ptr<node_t[]> nodes;
int size, height;
LazySegmentTree(int n): size(1), height(0) {
while (size < n || size < 8) size <<= 1, ++height;
nodes = unique_ptr<node_t[]>(new node_t[size<<1]);
for (int i = size - 1; i > 0; i--)
nodes[i].combine(nodes[i<<1], nodes[i<<1|1]);
}
void update(int _l, int _r, const U& v) {
push(_l); push(_r+1);
for (int l = _l + size, r = _r + size + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) nodes[l++].update(v);
if (r & 1) nodes[--r].update(v);
}
push(_l); push(_r+1);
for (int l = (_l+size) >> 1; l > 0; l >>= 1)
nodes[l].combine(nodes[l<<1], nodes[l<<1|1]);
for (int r = (_r+size) >> 1; r > 0; r >>= 1)
nodes[r].combine(nodes[r<<1], nodes[r<<1|1]);
}
void push(int p) {
for (int s = height; s > 0; s--) _push((p + size) >> s);
}
void _push(int i) {
if (nodes[i].has_lazy()) {
nodes[i<<1].update(nodes[i].lazy);
nodes[i<<1|1].update(nodes[i].lazy);
nodes[i].clear_lazy();
}
}
T query(int l, int r) {
push(l), push(r+1);
node_t le, ri, tmp;
for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) le = tmp.combine(le, nodes[l++]);
if (r & 1) ri = tmp.combine(nodes[--r], ri);
}
return tmp.combine(le, ri).query();
}
};
struct WallNode {
constexpr static ii lazy_null {0, 100'000};
using self_t = WallNode;
using val_t = int;
using upd_t = ii;
upd_t lazy{lazy_null};
upd_t v{};
val_t query() const { return v.x; }
void update(upd_t a) {
if (a.x > v.y) v = ii{a.x, a.x};
if (a.x > lazy.y) lazy = ii{a.x, a.x};
if (a.y < v.x) v = ii{a.y, a.y};
if (a.y < lazy.x) lazy = ii{a.y, a.y};
lazy.x = max(lazy.x, a.x);
lazy.y = min(lazy.y, a.y);
v.x = max(v.x, a.x);
v.y = min(v.y, a.y);
}
bool has_lazy() const { return lazy != lazy_null; }
void clear_lazy() { lazy = lazy_null; }
self_t combine(self_t const& le, self_t const& ri) {
if (le.v != ii{}) v = le.v;
if (ri.v != ii{}) v = ri.v;
return *this;
}
};
// int n = read(), m = read();
// LazySegmentTree<WallNode> tree(n+2);
void buildWal(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
LazySegmentTree<WallNode> tree(n+2);
for (int i = 0; i < k; i++) switch (op[i]) {
case 1: {
int l = left[i]+1, r = right[i]+1, h = height[i];
tree.update(l, r, ii{h, 100'000});
break;
}
case 2: {
int l = left[i]+1, r = right[i]+1, h = height[i];
tree.update(l, r, ii{0, h});
break;
}
default: __builtin_unreachable();
}
for (int i = 1; i <= n; i++) finalHeight[i-1] = tree.query(i, i);
}
/*
int main()
{
for (int l, r, h; m--;) switch(read()) {
case 1: {
l = read()+1, r = read()+1, h = read();
tree.update(l, r, ii{h, 100'000});
break;
}
case 2: {
l = read()+1, r = read()+1, h = read();
tree.update(l, r, ii{0, h});
break;
}
default: __builtin_unreachable();
}
for (int i = 1; i <= n; i++) printf("%d\n", tree.query(i, i));
return 0;
}
*/