| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 517023 | Jomnoi | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;
class Block {
public :
int val;
vector <pair <int, int>> lazy;
Block() : val(), lazy() {}
};
class SegmentTree {
protected :
const int N;
vector <Block> tree;
public :
SegmentTree(const int &n) : N(n) {
tree.resize(4 * n, Block());
}
void add(const int &recieve, vector <pair <int, int>> vec) {
for(auto &v : vec) {
if(v.first == 1) {
tree[recieve].lazy.clear();
}
else {
while(!tree[recieve].lazy.empty() and tree[recieve].lazy.back().first == 2) {
v.second = min(v.second, tree[recieve].lazy.back().second);
tree[recieve].lazy.pop_back();
}
}
tree[recieve].lazy.push_back(v);
}
}
void push_lazy(const int &idx, const int &l, const int &r) {
if(tree[idx].lazy.empty()) {
return;
}
if(l != r) {
add(idx * 2, tree[idx].lazy);
add(idx * 2 + 1, tree[idx].lazy);
}
for(auto [op, h] : tree[idx].lazy) {
if(op == 1) {
tree[idx].val = max(tree[idx].val, h);
}
else {
tree[idx].val = min(tree[idx].val, h);
}
}
tree[idx].lazy.clear();
}
void update(const int &idx, const int &l, const int &r, const int &ql, const int &qr, const int &op, const int &h) {
push_lazy(idx, l, r);
if(r < ql or qr < l) {
return;
}
if(ql <= l and r <= qr) {
add(idx, vector <pair <int, int>> {make_pair(op, h)});
push_lazy(idx, l, r);
return;
}
int mid = (l + r) / 2;
update(idx * 2, l, mid, ql, qr, op, h);
update(idx * 2 + 1, mid + 1, r, ql, qr, op, h);
}
void answer(const int &idx, const int &l, const int &r, int arr[]) {
push_lazy(idx, l, r);
if(l == r) {
arr[l] = tree[idx].val;
return;
}
int mid = (l + r) / 2;
answer(idx * 2, l, mid, arr);
answer(idx * 2 + 1, mid + 1, r, arr);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
SegmentTree st(n);
for(int i = 0; i < k; i++) {
st.update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
}
st.answer(1, 0, n - 1, finalHeight);
if(DEBUG) {
for(int i = 0; i < n; i++) {
cout << finalHeight[i] << " ";
}
}
}
int main() {
int n, k;
scanf(" %d %d", &n, &k);
int op[k], left[k], right[k], height[k], finalHeight[k];
for(int i = 0; i < k; i++) {
scanf(" %d %d %d %d", &op[i], &left[i], &right[i], &height[i]);
}
buildWall(n, k, op, left, right, height, finalHeight);
return 0;
}