| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 8581 |
2014-09-17T12:13:18 Z |
cki86201 |
Wall (IOI14_wall) |
C++ |
|
1120 ms |
65880 KB |
#include "wall.h"
#include<algorithm>
using namespace std;
int T[1<<22], P[1<<22], M[1<<22];
inline void update_node(int rt, int mode, int h){
if(mode == 1){
T[rt] = max(T[rt], h);
P[rt] = max(P[rt], h);
M[rt] = max(M[rt], P[rt]);
}
else{
T[rt] = min(T[rt], h);
M[rt] = min(M[rt], h);
P[rt] = min(P[rt], M[rt]);
}
}
void pushdown(int rt){
update_node(rt<<1, 2, M[rt]);
update_node(rt<<1, 1, P[rt]);
update_node(rt<<1|1, 2, M[rt]);
update_node(rt<<1|1, 1, P[rt]);
P[rt] = 0, M[rt] = 1e5 + 5;
}
void update(int rt, int s, int d, int mode, int l, int r, int h){
if(l <= s && d <= r){
update_node(rt, mode, h);
return;
}
pushdown(rt);
int m = (s+d)>>1;
if(l<=m)update(rt<<1, s, m, mode, l, r, h);
if(m<r)update(rt<<1|1, m+1, d, mode, l, r, h);
}
void get_ans(int rt, int s, int d, int &cnt, int arr[]){
if(s == d){
arr[cnt++] = T[rt];
return;
}
int m = (s+d)>>1;
pushdown(rt);
get_ans(rt<<1, s, m, cnt, arr);
get_ans(rt<<1|1, m+1, d, cnt, arr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int i;
for(i=0;i<1<<22;i++)M[i] = 1e5 + 5;
for(i=0;i<k;i++)update(1, 0, n-1, op[i], left[i], right[i], height[i]);
int cnt = 0;
get_ans(1, 0, n-1, cnt, finalHeight);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
50240 KB |
Output is correct |
| 2 |
Correct |
0 ms |
50240 KB |
Output is correct |
| 3 |
Correct |
0 ms |
50240 KB |
Output is correct |
| 4 |
Correct |
8 ms |
50240 KB |
Output is correct |
| 5 |
Correct |
8 ms |
50240 KB |
Output is correct |
| 6 |
Correct |
4 ms |
50240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
50240 KB |
Output is correct |
| 2 |
Correct |
184 ms |
58064 KB |
Output is correct |
| 3 |
Correct |
264 ms |
53488 KB |
Output is correct |
| 4 |
Correct |
760 ms |
58456 KB |
Output is correct |
| 5 |
Correct |
472 ms |
58456 KB |
Output is correct |
| 6 |
Correct |
492 ms |
58456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
50240 KB |
Output is correct |
| 2 |
Correct |
4 ms |
50240 KB |
Output is correct |
| 3 |
Correct |
8 ms |
50240 KB |
Output is correct |
| 4 |
Correct |
8 ms |
50240 KB |
Output is correct |
| 5 |
Correct |
8 ms |
50240 KB |
Output is correct |
| 6 |
Correct |
8 ms |
50240 KB |
Output is correct |
| 7 |
Correct |
0 ms |
50240 KB |
Output is correct |
| 8 |
Correct |
188 ms |
58064 KB |
Output is correct |
| 9 |
Correct |
252 ms |
53488 KB |
Output is correct |
| 10 |
Correct |
776 ms |
58456 KB |
Output is correct |
| 11 |
Correct |
488 ms |
58456 KB |
Output is correct |
| 12 |
Correct |
500 ms |
58456 KB |
Output is correct |
| 13 |
Correct |
4 ms |
50240 KB |
Output is correct |
| 14 |
Correct |
156 ms |
58064 KB |
Output is correct |
| 15 |
Correct |
48 ms |
50724 KB |
Output is correct |
| 16 |
Correct |
756 ms |
58456 KB |
Output is correct |
| 17 |
Correct |
484 ms |
58456 KB |
Output is correct |
| 18 |
Correct |
468 ms |
58456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
50240 KB |
Output is correct |
| 2 |
Correct |
4 ms |
50240 KB |
Output is correct |
| 3 |
Correct |
0 ms |
50240 KB |
Output is correct |
| 4 |
Correct |
8 ms |
50240 KB |
Output is correct |
| 5 |
Correct |
4 ms |
50240 KB |
Output is correct |
| 6 |
Correct |
8 ms |
50240 KB |
Output is correct |
| 7 |
Correct |
0 ms |
50240 KB |
Output is correct |
| 8 |
Correct |
180 ms |
58064 KB |
Output is correct |
| 9 |
Correct |
252 ms |
53488 KB |
Output is correct |
| 10 |
Correct |
760 ms |
58456 KB |
Output is correct |
| 11 |
Correct |
492 ms |
58456 KB |
Output is correct |
| 12 |
Correct |
492 ms |
58456 KB |
Output is correct |
| 13 |
Correct |
8 ms |
50240 KB |
Output is correct |
| 14 |
Correct |
180 ms |
58064 KB |
Output is correct |
| 15 |
Correct |
44 ms |
50724 KB |
Output is correct |
| 16 |
Correct |
740 ms |
58456 KB |
Output is correct |
| 17 |
Correct |
500 ms |
58456 KB |
Output is correct |
| 18 |
Correct |
496 ms |
58456 KB |
Output is correct |
| 19 |
Correct |
1120 ms |
65880 KB |
Output is correct |
| 20 |
Correct |
1112 ms |
65880 KB |
Output is correct |
| 21 |
Correct |
1104 ms |
65880 KB |
Output is correct |
| 22 |
Correct |
1104 ms |
65880 KB |
Output is correct |
| 23 |
Correct |
1092 ms |
65880 KB |
Output is correct |
| 24 |
Correct |
1092 ms |
65880 KB |
Output is correct |
| 25 |
Correct |
1112 ms |
65880 KB |
Output is correct |
| 26 |
Correct |
1120 ms |
65880 KB |
Output is correct |
| 27 |
Correct |
1108 ms |
65880 KB |
Output is correct |
| 28 |
Correct |
1096 ms |
65880 KB |
Output is correct |
| 29 |
Correct |
1092 ms |
65880 KB |
Output is correct |
| 30 |
Correct |
1108 ms |
65880 KB |
Output is correct |
