#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1 << 17;
int add[N << 2], del[N << 2];
void push(int i, int l, int r){
if(l != r){
add[i << 1] = max(add[i << 1], add[i]);
add[i << 1] = min(add[i << 1], del[i]);
del[i << 1] = max(del[i << 1], add[i]);
del[i << 1] = min(del[i << 1], del[i]);
add[i << 1 | 1] = max(add[i << 1 | 1], add[i]);
add[i << 1 | 1] = min(add[i << 1 | 1], del[i]);
del[i << 1 | 1] = max(del[i << 1 | 1], add[i]);
del[i << 1 | 1] = min(del[i << 1 | 1], del[i]);
add[i] = 0, del[i] = INF;
}
}
void updAdd(int l, int r, int i, int from, int to, int val){
push(i, from, to);
if (from > r || to < l)
return;
if (from >= l && to <= r)
{
add[i] = max(add[i], val);
del[i] = max(del[i], val);
push(i, from, to);
return;
}
int mid = (from + to) >> 1;
updAdd(l, r, i << 1, from, mid, val);
updAdd(l, r, i << 1 | 1, mid + 1, to, val);
}
void updDel(int l, int r, int i, int from, int to, int val){
push(i, from, to);
if(from > r || to < l) return;
if(from >= l && to <= r){
add[i] = min(add[i], val);
del[i] = min(del[i], val);
push(i, from, to);
return;
}
int mid = (from + to) >> 1;
updDel(l, r, i << 1, from, mid, val);
updDel(l, r, i << 1 | 1, mid + 1, to , val);
}
void pushall(int i, int l, int r){
if(l == r) return;
push(i, l, r);
int mid = (l + r) >> 1;
pushall(i << 1, l, mid);
pushall(i << 1 | 1, mid + 1, r);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]){
memset(del, INF, sizeof del);
for(int i = 0; i < k; i++){
if(op[i] == 1){
updAdd(l[i], r[i], 1, 0, N - 1, h[i]);
}
else{
updDel(l[i], r[i], 1, 0, N - 1, h[i]);
}
}
pushall(1, 0, N - 1);
for(int i = 0; i < n; i++){
ans[i] = min(add[i + N], del[i + N]);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3420 KB |
Output is correct |
2 |
Correct |
4 ms |
3420 KB |
Output is correct |
3 |
Correct |
3 ms |
3420 KB |
Output is correct |
4 |
Correct |
6 ms |
3628 KB |
Output is correct |
5 |
Correct |
6 ms |
3676 KB |
Output is correct |
6 |
Correct |
6 ms |
3672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3420 KB |
Output is correct |
2 |
Correct |
223 ms |
11268 KB |
Output is correct |
3 |
Correct |
158 ms |
6652 KB |
Output is correct |
4 |
Correct |
437 ms |
11912 KB |
Output is correct |
5 |
Correct |
252 ms |
12372 KB |
Output is correct |
6 |
Correct |
250 ms |
12236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3416 KB |
Output is correct |
2 |
Correct |
4 ms |
3416 KB |
Output is correct |
3 |
Correct |
3 ms |
3420 KB |
Output is correct |
4 |
Correct |
6 ms |
3608 KB |
Output is correct |
5 |
Correct |
6 ms |
3676 KB |
Output is correct |
6 |
Correct |
6 ms |
3928 KB |
Output is correct |
7 |
Correct |
2 ms |
3420 KB |
Output is correct |
8 |
Correct |
217 ms |
11272 KB |
Output is correct |
9 |
Correct |
161 ms |
6860 KB |
Output is correct |
10 |
Correct |
441 ms |
11924 KB |
Output is correct |
11 |
Correct |
265 ms |
12316 KB |
Output is correct |
12 |
Correct |
249 ms |
12368 KB |
Output is correct |
13 |
Correct |
2 ms |
3416 KB |
Output is correct |
14 |
Correct |
223 ms |
11480 KB |
Output is correct |
15 |
Correct |
27 ms |
3920 KB |
Output is correct |
16 |
Correct |
448 ms |
12168 KB |
Output is correct |
17 |
Correct |
254 ms |
12004 KB |
Output is correct |
18 |
Correct |
253 ms |
12000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3420 KB |
Output is correct |
2 |
Correct |
4 ms |
3420 KB |
Output is correct |
3 |
Correct |
3 ms |
3420 KB |
Output is correct |
4 |
Correct |
6 ms |
3676 KB |
Output is correct |
5 |
Correct |
6 ms |
3484 KB |
Output is correct |
6 |
Correct |
6 ms |
3676 KB |
Output is correct |
7 |
Correct |
2 ms |
3416 KB |
Output is correct |
8 |
Correct |
216 ms |
11240 KB |
Output is correct |
9 |
Correct |
158 ms |
6736 KB |
Output is correct |
10 |
Correct |
438 ms |
11908 KB |
Output is correct |
11 |
Correct |
253 ms |
12372 KB |
Output is correct |
12 |
Correct |
249 ms |
12208 KB |
Output is correct |
13 |
Correct |
2 ms |
3420 KB |
Output is correct |
14 |
Correct |
228 ms |
11240 KB |
Output is correct |
15 |
Correct |
27 ms |
4036 KB |
Output is correct |
16 |
Correct |
449 ms |
12400 KB |
Output is correct |
17 |
Correct |
253 ms |
12112 KB |
Output is correct |
18 |
Correct |
256 ms |
12112 KB |
Output is correct |
19 |
Runtime error |
151 ms |
29268 KB |
Execution killed with signal 11 |
20 |
Halted |
0 ms |
0 KB |
- |