#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2000001;
int mn[4 * N], mx[4 * N];
int n, k;
void upd(int MN, int MX, int now) {
mn[now] = max(MN, min(mn[now], mx[now]));
mx[now] = min(MX, max(mn[now], mx[now]));
}
void push(int now) {
upd(mn[now], mx[now], 2 * now);
upd(mn[now], mx[now], 2 * now + 1);
mn[now] = 0, mx[now] = 1e9;
}
void build(int now = 1, int l = 1, int r = n) {
mn[now] = 0;
mx[now] = 1e9;
if (l == r) return;
int mid = (l + r) / 2;
build(2 * now, l, mid);
build(2 * now + 1, mid + 1, r);
}
void update(int ql, int qr, int w, int op, int now = 1, int l = 1, int r = n) {
if (l > qr || r < ql) return;
if (ql <= l && r <= qr) {
if (op == 1) upd(w, 1e9, now);
else upd(0, w, now);
return;
}
push(now);
int mid = (l + r) / 2;
update(ql, qr, w, op, 2 * now, l, mid);
update(ql, qr, w, op, 2 * now + 1, mid + 1, r);
}
void cal(int finalHeight[], int now = 1, int l = 1, int r = n) {
if (l == r) {
finalHeight[l - 1] = min(mn[now], mx[now]);
return;
}
push(now);
int mid = (l + r) / 2;
cal(finalHeight, 2 * now, l, mid);
cal(finalHeight, 2 * now + 1, mid + 1, r);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
n = N, k = K;
build();
for (int i = 0;i < k;i++) {
update(left[i] + 1, right[i] + 1, height[i], op[i]);
// cal(finalHeight);
// for (int i = 0;i < n;i++) {
// cout << finalHeight[i] << ' ';
// }
// cout << '\n';
}
cal(finalHeight);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
912 KB |
Output is correct |
| 5 |
Correct |
3 ms |
904 KB |
Output is correct |
| 6 |
Correct |
3 ms |
900 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
87 ms |
13908 KB |
Output is correct |
| 3 |
Correct |
115 ms |
6740 KB |
Output is correct |
| 4 |
Correct |
342 ms |
20308 KB |
Output is correct |
| 5 |
Correct |
193 ms |
21332 KB |
Output is correct |
| 6 |
Correct |
196 ms |
19796 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
4 ms |
860 KB |
Output is correct |
| 5 |
Correct |
3 ms |
904 KB |
Output is correct |
| 6 |
Correct |
3 ms |
860 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
83 ms |
14056 KB |
Output is correct |
| 9 |
Correct |
116 ms |
8000 KB |
Output is correct |
| 10 |
Correct |
327 ms |
20348 KB |
Output is correct |
| 11 |
Correct |
191 ms |
21332 KB |
Output is correct |
| 12 |
Correct |
185 ms |
19952 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
92 ms |
13844 KB |
Output is correct |
| 15 |
Correct |
19 ms |
2140 KB |
Output is correct |
| 16 |
Correct |
326 ms |
20572 KB |
Output is correct |
| 17 |
Correct |
200 ms |
20056 KB |
Output is correct |
| 18 |
Correct |
197 ms |
20332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
344 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
860 KB |
Output is correct |
| 5 |
Correct |
3 ms |
860 KB |
Output is correct |
| 6 |
Correct |
3 ms |
860 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
85 ms |
13936 KB |
Output is correct |
| 9 |
Correct |
121 ms |
8016 KB |
Output is correct |
| 10 |
Correct |
326 ms |
20332 KB |
Output is correct |
| 11 |
Correct |
206 ms |
21332 KB |
Output is correct |
| 12 |
Correct |
183 ms |
20000 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
89 ms |
13892 KB |
Output is correct |
| 15 |
Correct |
18 ms |
2136 KB |
Output is correct |
| 16 |
Correct |
340 ms |
20564 KB |
Output is correct |
| 17 |
Correct |
205 ms |
20032 KB |
Output is correct |
| 18 |
Correct |
208 ms |
20052 KB |
Output is correct |
| 19 |
Correct |
469 ms |
69460 KB |
Output is correct |
| 20 |
Correct |
463 ms |
67156 KB |
Output is correct |
| 21 |
Correct |
467 ms |
69460 KB |
Output is correct |
| 22 |
Correct |
459 ms |
67160 KB |
Output is correct |
| 23 |
Correct |
458 ms |
67152 KB |
Output is correct |
| 24 |
Correct |
460 ms |
67152 KB |
Output is correct |
| 25 |
Correct |
450 ms |
66900 KB |
Output is correct |
| 26 |
Correct |
456 ms |
69460 KB |
Output is correct |
| 27 |
Correct |
455 ms |
69456 KB |
Output is correct |
| 28 |
Correct |
449 ms |
66900 KB |
Output is correct |
| 29 |
Correct |
450 ms |
67152 KB |
Output is correct |
| 30 |
Correct |
472 ms |
67004 KB |
Output is correct |
