#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
void chmin (int &x, int y) {
x = min(x, y);
}
void chmax(int &x, int y) {
x = max(x, y);
}
struct pp {
int mx = 0, mn = 1e9;
};
struct SegmentTree {
vector <pp> tree;
void prop (int l, int r, int node) {
if (l == r) return;
chmin(tree[tl].mn, tree[node].mn);
chmax(tree[tl].mn, tree[node].mx);
chmax(tree[tl].mx, tree[node].mx);
chmin(tree[tl].mx, tree[node].mn);
chmin(tree[tr].mn, tree[node].mn);
chmax(tree[tr].mn, tree[node].mx);
chmax(tree[tr].mx, tree[node].mx);
chmin(tree[tr].mx, tree[node].mn);
tree[node].mn = 1e9; tree[node].mx = 0;
}
void update (int l, int r, int a, int b, int h, int t, int node) {
prop(l, r, node);
if (l > b || r < a) return;
if (l >= a && r <= b) {
if (t == 2) {
chmin(tree[node].mn, h);
chmin(tree[node].mx, h);
} else {
chmax(tree[node].mn, h);
chmax(tree[node].mx, h);
}
prop(l, r, node);
return;
}
update(l, mid, a, b, h, t, tl);
update(mid + 1, r, a, b, h, t, tr);
}
void dfs (int l, int r, int node) {
prop(l, r, node);
if (l == r) return;
dfs(l, mid, tl);
dfs(mid + 1, r, tr);
}
pp get (int l, int r, int a, int node) {
if (l == r) {
return tree[node];
}
if (mid < a) return get(mid + 1, r, a, tr);
return get(l, mid, a, tl);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
SegmentTree cur; cur.tree.resize(2 * n);
for (int i = 0; i < k; i++) {
left[i]++; right[i]++;
}
for (int i = 0; i < k; i++) {
cur.update(1, n, left[i], right[i], height[i], op[i], 1);
}
cur.dfs(1, n, 1);
for (int i = 0; i < n; i++) {
auto k = cur.get(1, n, i + 1, 1);
finalHeight[i] = min(k.mn, k.mx);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
6 ms |
704 KB |
Output is correct |
| 5 |
Correct |
5 ms |
952 KB |
Output is correct |
| 6 |
Correct |
5 ms |
700 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
101 ms |
13908 KB |
Output is correct |
| 3 |
Correct |
167 ms |
4688 KB |
Output is correct |
| 4 |
Correct |
484 ms |
19688 KB |
Output is correct |
| 5 |
Correct |
299 ms |
20276 KB |
Output is correct |
| 6 |
Correct |
287 ms |
18696 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
6 ms |
700 KB |
Output is correct |
| 5 |
Correct |
5 ms |
700 KB |
Output is correct |
| 6 |
Correct |
5 ms |
700 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
102 ms |
13908 KB |
Output is correct |
| 9 |
Correct |
200 ms |
7804 KB |
Output is correct |
| 10 |
Correct |
479 ms |
19728 KB |
Output is correct |
| 11 |
Correct |
305 ms |
20308 KB |
Output is correct |
| 12 |
Correct |
285 ms |
18660 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
105 ms |
13908 KB |
Output is correct |
| 15 |
Correct |
28 ms |
1784 KB |
Output is correct |
| 16 |
Correct |
511 ms |
19692 KB |
Output is correct |
| 17 |
Correct |
301 ms |
19284 KB |
Output is correct |
| 18 |
Correct |
298 ms |
19028 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
700 KB |
Output is correct |
| 5 |
Correct |
5 ms |
700 KB |
Output is correct |
| 6 |
Correct |
5 ms |
700 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
103 ms |
14032 KB |
Output is correct |
| 9 |
Correct |
178 ms |
7760 KB |
Output is correct |
| 10 |
Correct |
483 ms |
19700 KB |
Output is correct |
| 11 |
Correct |
304 ms |
20328 KB |
Output is correct |
| 12 |
Correct |
296 ms |
18700 KB |
Output is correct |
| 13 |
Correct |
0 ms |
344 KB |
Output is correct |
| 14 |
Correct |
105 ms |
13904 KB |
Output is correct |
| 15 |
Correct |
35 ms |
1624 KB |
Output is correct |
| 16 |
Correct |
488 ms |
19684 KB |
Output is correct |
| 17 |
Correct |
298 ms |
19028 KB |
Output is correct |
| 18 |
Correct |
290 ms |
19116 KB |
Output is correct |
| 19 |
Correct |
806 ms |
57940 KB |
Output is correct |
| 20 |
Correct |
797 ms |
57684 KB |
Output is correct |
| 21 |
Correct |
793 ms |
57824 KB |
Output is correct |
| 22 |
Correct |
784 ms |
57596 KB |
Output is correct |
| 23 |
Correct |
788 ms |
57580 KB |
Output is correct |
| 24 |
Correct |
807 ms |
57692 KB |
Output is correct |
| 25 |
Correct |
855 ms |
57688 KB |
Output is correct |
| 26 |
Correct |
799 ms |
57692 KB |
Output is correct |
| 27 |
Correct |
787 ms |
57604 KB |
Output is correct |
| 28 |
Correct |
814 ms |
57688 KB |
Output is correct |
| 29 |
Correct |
769 ms |
57940 KB |
Output is correct |
| 30 |
Correct |
807 ms |
57940 KB |
Output is correct |
