# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
1112548 |
2024-11-14T09:58:55 Z |
farica |
벽 (IOI14_wall) |
C++14 |
|
708 ms |
224688 KB |
#include <bits/stdc++.h>
#include <wall.h>
using namespace std;
const int MAX_N = 1e5;
struct Segm {
int x, L, R;
};
vector<Segm>segm;
void push(int pos, int l, int r) {
if(l==r) {
if(segm[pos].L > segm[pos].x) segm[pos].x = segm[pos].L;
if(segm[pos].R < segm[pos].x) segm[pos].x = segm[pos].R;
segm[pos].L = 0, segm[pos].R = MAX_N;
return;
}
if(segm[pos].L) {
segm[2*pos+1].L = max(segm[2*pos+1].L, segm[pos].L);
if(segm[2*pos+1].R < segm[pos].L) segm[2*pos+1].R = segm[pos].L;
segm[2*pos+2].L = max(segm[2*pos+2].L, segm[pos].L);
if(segm[2*pos+2].R < segm[pos].L) segm[2*pos+2].R = segm[pos].L;
segm[pos].L = 0;
}
if(segm[pos].R != MAX_N) {
segm[2*pos+1].R = min(segm[2*pos+1].R, segm[pos].R);
if(segm[2*pos+1].L > segm[pos].R) segm[2*pos+1].L = segm[pos].R;
segm[2*pos+2].R = min(segm[2*pos+2].R, segm[pos].R);
if(segm[2*pos+2].L > segm[pos].R) segm[2*pos+2].L = segm[pos].R;
segm[pos].R = MAX_N;
}
}
void update(int pos, int l, int r, int L, int R, int val, int type) {
if(r < L or l > R) return;
push(pos, l, r);
if(l >= L && r <= R) {
if(type == 1) segm[pos].L = max(segm[pos].L, val);
else segm[pos].R = min(segm[pos].R, val);
return;
}
int mid = (l+r)/2;
update(2*pos+1, l, mid, L, R, val, type);
update(2*pos+2, mid+1, r, L, R, val, type);
}
int query(int pos, int l, int r, int x) {
push(pos, l, r);
if(l == r) return segm[pos].x;
int mid = (l+r)/2;
if(mid >= x) return query(2*pos+1, l, mid, x);
else return query(2*pos+2, mid+1, r, x);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
Segm tmp;
tmp.x = 0;
tmp.L = 0;
tmp.R = MAX_N;
segm.assign(8*n, tmp);
for(int i=0; i<k; ++i) {
update(1, 1, n, left[i]+1, right[i]+1, height[i], op[i]);
}
for(int i=1; i<=n; ++i) {
finalHeight[i-1] = query(1, 1, n, i);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
336 KB |
Output is correct |
4 |
Correct |
7 ms |
1360 KB |
Output is correct |
5 |
Correct |
5 ms |
1360 KB |
Output is correct |
6 |
Correct |
5 ms |
1360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
92 ms |
8264 KB |
Output is correct |
3 |
Correct |
117 ms |
5448 KB |
Output is correct |
4 |
Correct |
314 ms |
18172 KB |
Output is correct |
5 |
Correct |
185 ms |
18588 KB |
Output is correct |
6 |
Correct |
177 ms |
18504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
488 KB |
Output is correct |
4 |
Correct |
7 ms |
1360 KB |
Output is correct |
5 |
Correct |
5 ms |
1360 KB |
Output is correct |
6 |
Correct |
5 ms |
1360 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
85 ms |
8088 KB |
Output is correct |
9 |
Correct |
114 ms |
5448 KB |
Output is correct |
10 |
Correct |
336 ms |
27848 KB |
Output is correct |
11 |
Correct |
191 ms |
28744 KB |
Output is correct |
12 |
Correct |
182 ms |
27260 KB |
Output is correct |
13 |
Correct |
1 ms |
336 KB |
Output is correct |
14 |
Correct |
98 ms |
14076 KB |
Output is correct |
15 |
Correct |
33 ms |
3152 KB |
Output is correct |
16 |
Correct |
578 ms |
27976 KB |
Output is correct |
17 |
Correct |
208 ms |
27332 KB |
Output is correct |
18 |
Correct |
197 ms |
27464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
336 KB |
Output is correct |
4 |
Correct |
6 ms |
1360 KB |
Output is correct |
5 |
Correct |
5 ms |
1360 KB |
Output is correct |
6 |
Correct |
5 ms |
1316 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
85 ms |
8136 KB |
Output is correct |
9 |
Correct |
116 ms |
5476 KB |
Output is correct |
10 |
Correct |
338 ms |
27720 KB |
Output is correct |
11 |
Correct |
193 ms |
28744 KB |
Output is correct |
12 |
Correct |
196 ms |
27348 KB |
Output is correct |
13 |
Correct |
1 ms |
336 KB |
Output is correct |
14 |
Correct |
113 ms |
14004 KB |
Output is correct |
15 |
Correct |
32 ms |
3152 KB |
Output is correct |
16 |
Correct |
551 ms |
28084 KB |
Output is correct |
17 |
Correct |
199 ms |
27468 KB |
Output is correct |
18 |
Correct |
217 ms |
27464 KB |
Output is correct |
19 |
Correct |
666 ms |
224584 KB |
Output is correct |
20 |
Correct |
672 ms |
222084 KB |
Output is correct |
21 |
Correct |
700 ms |
224680 KB |
Output is correct |
22 |
Correct |
708 ms |
222024 KB |
Output is correct |
23 |
Correct |
664 ms |
222096 KB |
Output is correct |
24 |
Correct |
683 ms |
222136 KB |
Output is correct |
25 |
Correct |
694 ms |
222024 KB |
Output is correct |
26 |
Correct |
689 ms |
224516 KB |
Output is correct |
27 |
Correct |
694 ms |
224688 KB |
Output is correct |
28 |
Correct |
693 ms |
222024 KB |
Output is correct |
29 |
Correct |
660 ms |
222028 KB |
Output is correct |
30 |
Correct |
666 ms |
222112 KB |
Output is correct |