| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1323384 | orgiloogii | 벽 (IOI14_wall) | C++20 | 0 ms | 0 KiB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
vector <int> lz, sum;
vector <bool> has;
vector <int> lo, hi;
void propagate(int id) {
int x = id * 2 + 1;
int y = x + 1;
lo[x] = max(lo[x], lo[id]);
hi[x] = max(hi[x], lo[id]);
lo[x] = min(lo[x], hi[id]);
hi[x] = min(hi[x], hi[id]);
lo[y] = max(lo[y], lo[id]);
hi[y] = max(hi[y], lo[id]);
lo[y] = min(lo[y], hi[id]);
hi[y] = min(hi[y], hi[id]);
lo[id] = -1;
hi[id] = LLONG_MAX;
}
int query(int id, int l, int r, int i, int val) {
int cur = max(val, lo[id]);
cur = min(cur, hi[id]);
if (l == r)
return cur;
propagate(id);
int mid = (l + r) / 2, x = id * 2 + 1, y = x + 1, a;
if (i <= mid)
return query(x, l, mid, i, cur);
else
return query(y, mid + 1, r, i, cur);
}
void update(int id, int l, int r, int L, int R, int k) {
if (L <= l && r <= R) {
if (k > 0)
lo[id] = max(lo[id], k);
else
hi[id] = min(hi[id], -k);
return;
}
propagate(id);
int m = (l + r) / 2;
if (R <= m) {
update(id * 2 + 1, l, m, L, R, k);
}
else if (L > m) {
update(id * 2 + 2, m + 1, r, L, R, k);
}
else {
update(id * 2 + 1, l, m, L, m, k);
update(id * 2 + 2, m + 1, r, m + 1, R, k);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
lz.resize(4 * n, 0);
has.resize(4 * n, 0);
lo.assign(4 * n, 0);
hi.assign(4 * n, LLONG_MAX);
for (int i = 0;i < k;i++) {
if (op[i] == 1) {
update(0, 0, n - 1, left[i], right[i], height[i]);
}
else {
update(0, 0, n - 1, left[i], right[i], -height[i]);
}
}
for (int i = 0;i < n;i++) {
finalHeight[i] = query(0, 0, n - 1, i, 0);
}
for (int i = 0;i < n;i++) {
cout << finalHeight[i] << " ";
}
cout << endl;
}
//
//signed main() {
// int n, k;
// cin >> n >> k;
// int op[k], left[k], right[k], height[k], ans[n];
// for (int i = 0;i < k;i++) {
// cin >> op[i] >> left[i] >> right[i] >> height[i];
// }
// buildWall(n, k, op, left, right, height, ans);
//}