#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2e6 + 10;
int a[N], mn[N << 2], mx[N << 2];
void applymin(int node, int h) {
mn[node] = min(mn[node], h);
mx[node] = min(mx[node], mn[node]);
}
void applymax(int node, int h) {
mx[node] = max(mx[node], h);
mn[node] = max(mn[node], mx[node]);
}
void shift(int node) {
applymin(node << 1, mn[node]);
applymin(node << 1 | 1, mn[node]);
applymax(node << 1, mx[node]);
applymax(node << 1 | 1, mx[node]);
mx[node] = 0;
mn[node] = INT_MAX;
}
void update(int node, int l, int r, int op, int i, int j, int h) {
if(r < i || l > j) return;
if(i <= l && r <= j) {
if(op == 1) applymax(node, h);
else applymin(node, h);
return;
} shift(node);
int m = l + r >> 1;
update(node << 1, l, m, op, i, j, h);
update(node << 1 | 1, m + 1, r, op, i, j, h);
}
void get(int node, int l, int r) {
if(l == r) {
a[l] = min(a[l], mn[node]);
a[l] = max(a[l], mx[node]);
return;
} int m = l + r >> 1;
shift(node);
get(node << 1, l, m);
get(node << 1 | 1, m + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
fill(mn, mn + (n << 2), INT_MAX);
fill(mx, mx + (n << 2), 0);
for(int i = 0; i < k; i++) {
update(1, 0, n - 1, op[i], left[i], right[i], height[i]);
} get(1, 0, n - 1);
for(int i = 0; i < n; i++)
finalHeight[i] = a[i];
}
Compilation message
wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:31:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
wall.cpp: In function 'void get(int, int, int)':
wall.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
} int m = l + r >> 1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
7 ms |
488 KB |
Output is correct |
| 3 |
Correct |
4 ms |
488 KB |
Output is correct |
| 4 |
Correct |
13 ms |
908 KB |
Output is correct |
| 5 |
Correct |
8 ms |
924 KB |
Output is correct |
| 6 |
Correct |
7 ms |
996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
996 KB |
Output is correct |
| 2 |
Correct |
249 ms |
8296 KB |
Output is correct |
| 3 |
Correct |
217 ms |
8296 KB |
Output is correct |
| 4 |
Correct |
691 ms |
12484 KB |
Output is correct |
| 5 |
Correct |
396 ms |
13124 KB |
Output is correct |
| 6 |
Correct |
451 ms |
13124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
13124 KB |
Output is correct |
| 2 |
Correct |
5 ms |
13124 KB |
Output is correct |
| 3 |
Correct |
4 ms |
13124 KB |
Output is correct |
| 4 |
Correct |
9 ms |
13124 KB |
Output is correct |
| 5 |
Correct |
8 ms |
13124 KB |
Output is correct |
| 6 |
Correct |
9 ms |
13124 KB |
Output is correct |
| 7 |
Correct |
4 ms |
13124 KB |
Output is correct |
| 8 |
Correct |
337 ms |
13124 KB |
Output is correct |
| 9 |
Correct |
291 ms |
13124 KB |
Output is correct |
| 10 |
Correct |
744 ms |
13124 KB |
Output is correct |
| 11 |
Correct |
396 ms |
13208 KB |
Output is correct |
| 12 |
Correct |
403 ms |
13208 KB |
Output is correct |
| 13 |
Correct |
2 ms |
13208 KB |
Output is correct |
| 14 |
Correct |
251 ms |
13208 KB |
Output is correct |
| 15 |
Correct |
55 ms |
13208 KB |
Output is correct |
| 16 |
Correct |
700 ms |
13208 KB |
Output is correct |
| 17 |
Correct |
436 ms |
13208 KB |
Output is correct |
| 18 |
Correct |
436 ms |
13208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
13208 KB |
Output is correct |
| 2 |
Correct |
5 ms |
13208 KB |
Output is correct |
| 3 |
Correct |
4 ms |
13208 KB |
Output is correct |
| 4 |
Correct |
10 ms |
13208 KB |
Output is correct |
| 5 |
Correct |
8 ms |
13208 KB |
Output is correct |
| 6 |
Correct |
11 ms |
13208 KB |
Output is correct |
| 7 |
Correct |
2 ms |
13208 KB |
Output is correct |
| 8 |
Correct |
177 ms |
13208 KB |
Output is correct |
| 9 |
Correct |
219 ms |
13208 KB |
Output is correct |
| 10 |
Correct |
734 ms |
13208 KB |
Output is correct |
| 11 |
Correct |
505 ms |
13208 KB |
Output is correct |
| 12 |
Correct |
419 ms |
13260 KB |
Output is correct |
| 13 |
Correct |
3 ms |
13260 KB |
Output is correct |
| 14 |
Correct |
241 ms |
13260 KB |
Output is correct |
| 15 |
Correct |
40 ms |
13260 KB |
Output is correct |
| 16 |
Correct |
775 ms |
13260 KB |
Output is correct |
| 17 |
Correct |
507 ms |
13260 KB |
Output is correct |
| 18 |
Correct |
503 ms |
13260 KB |
Output is correct |
| 19 |
Correct |
971 ms |
96904 KB |
Output is correct |
| 20 |
Correct |
939 ms |
96904 KB |
Output is correct |
| 21 |
Correct |
927 ms |
96904 KB |
Output is correct |
| 22 |
Correct |
841 ms |
96904 KB |
Output is correct |
| 23 |
Correct |
976 ms |
96904 KB |
Output is correct |
| 24 |
Correct |
906 ms |
96904 KB |
Output is correct |
| 25 |
Correct |
801 ms |
96904 KB |
Output is correct |
| 26 |
Correct |
1185 ms |
96904 KB |
Output is correct |
| 27 |
Correct |
1014 ms |
96904 KB |
Output is correct |
| 28 |
Correct |
896 ms |
96904 KB |
Output is correct |
| 29 |
Correct |
855 ms |
96904 KB |
Output is correct |
| 30 |
Correct |
863 ms |
96904 KB |
Output is correct |
