#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int seg1[8000005], seg2[8000005]; // min, max
int inf = 1e9;
int mn[2000005], mx[2000005];
void push(int x, int l, int r) {
if(l==r) return;
seg1[x*2] = min(seg1[x*2], seg1[x]);
seg2[x*2] = min(seg2[x*2], seg1[x]);
seg1[x*2] = max(seg1[x*2], seg2[x]);
seg2[x*2] = max(seg2[x*2], seg2[x]);
seg1[x*2+1] = min(seg1[x*2+1], seg1[x]);
seg2[x*2+1] = min(seg2[x*2+1], seg1[x]);
seg1[x*2+1] = max(seg1[x*2+1], seg2[x]);
seg2[x*2+1] = max(seg2[x*2+1], seg2[x]);
seg1[x] = inf; seg2[x] = -inf;
}
void upd(int x, int l, int r, int ll, int rr, int tp, int val) {
if(l > rr || r < ll) return;
push(x, l, r);
if(ll <= l && r <= rr) {
if(tp==1) { // max operation
seg1[x] = max(seg1[x], val);
seg2[x] = max(seg2[x], val);
} else {
seg1[x] = min(seg1[x], val);
seg2[x] = min(seg2[x], val);
}
} else {
upd(x*2, l, (l+r)/2, ll, rr, tp, val);
upd(x*2+1, (l+r)/2+1, r, ll, rr, tp, val);
}
}
void qry(int x, int l, int r) {
push(x, l, r);
if(l==r) {
mn[l] = seg1[x];
mx[l] = seg2[x];
} else {
qry(x*2, l, (l+r)/2);
qry(x*2+1, (l+r)/2+1, r);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
memset(seg1, inf, sizeof(seg1));
memset(seg2, -inf, sizeof(seg2));
for(int i=0; i<k; i++) {
upd(1, 0, n-1, left[i], right[i], op[i], height[i]);
}
qry(1, 0, n-1);
for(int i=0; i<n; i++) {
finalHeight[i] = max(min(0, mn[i]), mx[i]);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
24 ms |
62812 KB |
Output is correct |
| 2 |
Correct |
27 ms |
63004 KB |
Output is correct |
| 3 |
Correct |
26 ms |
62884 KB |
Output is correct |
| 4 |
Correct |
28 ms |
63240 KB |
Output is correct |
| 5 |
Correct |
28 ms |
63248 KB |
Output is correct |
| 6 |
Correct |
28 ms |
63220 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
24 ms |
62992 KB |
Output is correct |
| 2 |
Correct |
156 ms |
76588 KB |
Output is correct |
| 3 |
Correct |
176 ms |
70176 KB |
Output is correct |
| 4 |
Correct |
450 ms |
81672 KB |
Output is correct |
| 5 |
Correct |
300 ms |
82708 KB |
Output is correct |
| 6 |
Correct |
287 ms |
81176 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
62936 KB |
Output is correct |
| 2 |
Correct |
27 ms |
63060 KB |
Output is correct |
| 3 |
Correct |
25 ms |
62924 KB |
Output is correct |
| 4 |
Correct |
29 ms |
63200 KB |
Output is correct |
| 5 |
Correct |
29 ms |
63252 KB |
Output is correct |
| 6 |
Correct |
28 ms |
63204 KB |
Output is correct |
| 7 |
Correct |
24 ms |
62856 KB |
Output is correct |
| 8 |
Correct |
152 ms |
76588 KB |
Output is correct |
| 9 |
Correct |
175 ms |
70220 KB |
Output is correct |
| 10 |
Correct |
538 ms |
81680 KB |
Output is correct |
| 11 |
Correct |
293 ms |
82704 KB |
Output is correct |
| 12 |
Correct |
298 ms |
81144 KB |
Output is correct |
| 13 |
Correct |
22 ms |
62888 KB |
Output is correct |
| 14 |
Correct |
148 ms |
76548 KB |
Output is correct |
| 15 |
Correct |
51 ms |
64332 KB |
Output is correct |
| 16 |
Correct |
448 ms |
82004 KB |
Output is correct |
| 17 |
Correct |
303 ms |
81408 KB |
Output is correct |
| 18 |
Correct |
306 ms |
81404 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
62820 KB |
Output is correct |
| 2 |
Correct |
24 ms |
63064 KB |
Output is correct |
| 3 |
Correct |
24 ms |
62928 KB |
Output is correct |
| 4 |
Correct |
30 ms |
63224 KB |
Output is correct |
| 5 |
Correct |
28 ms |
63152 KB |
Output is correct |
| 6 |
Correct |
28 ms |
63180 KB |
Output is correct |
| 7 |
Correct |
23 ms |
62924 KB |
Output is correct |
| 8 |
Correct |
158 ms |
76520 KB |
Output is correct |
| 9 |
Correct |
185 ms |
70160 KB |
Output is correct |
| 10 |
Correct |
467 ms |
81784 KB |
Output is correct |
| 11 |
Correct |
288 ms |
82724 KB |
Output is correct |
| 12 |
Correct |
297 ms |
81148 KB |
Output is correct |
| 13 |
Correct |
24 ms |
62796 KB |
Output is correct |
| 14 |
Correct |
150 ms |
76564 KB |
Output is correct |
| 15 |
Correct |
49 ms |
64232 KB |
Output is correct |
| 16 |
Correct |
479 ms |
82124 KB |
Output is correct |
| 17 |
Correct |
296 ms |
81356 KB |
Output is correct |
| 18 |
Correct |
303 ms |
81324 KB |
Output is correct |
| 19 |
Correct |
704 ms |
114968 KB |
Output is correct |
| 20 |
Correct |
693 ms |
112456 KB |
Output is correct |
| 21 |
Correct |
696 ms |
114872 KB |
Output is correct |
| 22 |
Correct |
719 ms |
112456 KB |
Output is correct |
| 23 |
Correct |
687 ms |
112444 KB |
Output is correct |
| 24 |
Correct |
712 ms |
112444 KB |
Output is correct |
| 25 |
Correct |
705 ms |
112432 KB |
Output is correct |
| 26 |
Correct |
719 ms |
114876 KB |
Output is correct |
| 27 |
Correct |
690 ms |
114924 KB |
Output is correct |
| 28 |
Correct |
679 ms |
112408 KB |
Output is correct |
| 29 |
Correct |
682 ms |
112460 KB |
Output is correct |
| 30 |
Correct |
678 ms |
112528 KB |
Output is correct |
