| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 990157 | andrew | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
bool need_update = 0;
int l = -1e9, r = 1e9;
node *left = nullptr, *right = nullptr;
};
void build(node *v, int l, int r) {
if (l == r) {
v -> l = v -> r = 0;
} else {
int m = (l + r) >> 1;
v->left = new node();
v->right = new node();
build(v->left, l, m);
build(v->right, m + 1, r);
}
}
void update(node *v, int tl, int tr, int l, int r, int op, int val) {
if (l > r) return;
if (tl == l && tr == r) {
if (op == 1) {
v->l = max(v->l, val);
v->r = max(v->r, val);
v->need_update = 1;
} else {
v->l = min(v->l, val);
v->r = min(v->r, val);
v->need_update = 1;
}
return;
}
int tm = (tl + tr) >> 1;
if (v->need_update) {
v->left->l = max(v->left->l, v->l);
v->left->r = max(v->left->r, v->l);
v->left->l = min(v->left->l, v->r);
v->left->r = min(v->left->r, v->r);
v->left->need_update = 1;
v->right->l = max(v->right->l, v->l);
v->right->r = max(v->right->r, v->l);
v->right->l = min(v->right->l, v->r);
v->right->r = min(v->right->r, v->r);
v->right->need_update = 1;
v->need_update = 0;
v->l = -1e9;
v->r = 1e9;
}
update(v->left, tl, tm, l, min(r, tm), op, val);
update(v->right, tm + 1, tr, max(l, tm + 1), r, op, val);
}
void solve(node *v, int tl, int tr) {
if (tl == tr) {
cout << v->l << '\n';
} else {
int tm = (tl + tr) >> 1;
if (v->need_update) {
v->left->l = max(v->left->l, v->l);
v->left->r = max(v->left->r, v->l);
v->left->l = min(v->left->l, v->r);
v->left->r = min(v->left->r, v->r);
v->left->need_update = 1;
v->right->l = max(v->right->l, v->l);
v->right->r = max(v->right->r, v->l);
v->right->l = min(v->right->l, v->r);
v->right->r = min(v->right->r, v->r);
v->need_update = 0;
}
solve(v->left, tl, tm);
solve(v->right, tm + 1, tr);
}
}
int main(){
ios_base :: sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
node *root = new node();
build(root, 0, n - 1);
for (int i = 0; i < q; i++) {
int op, l, r, x;
cin >> op >> l >> r >> x;
update(root, 0, n - 1, l, r, op, x);
}
solve(root, 0, n - 1);
return 0;
}