# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
129204 |
2019-07-11T20:26:22 Z |
anayk |
벽 (IOI14_wall) |
C++14 |
|
1164 ms |
69724 KB |
#include <iostream>
#include "wall.h"
#define MAXN 2000005
#define MAXH 100000
struct data
{
int low, high;
};
data seg[4*MAXN];
int N;
data add(data x, bool type, int val)
{
if(type)
x.high = std::min(x.high, val);
else
x.low = std::max(x.low, val);
if(x.low >= x.high)
{
if(type)
x.low = x.high;
else
x.high = x.low;
}
return x;
}
void shift(int id)
{
seg[2*id] = add(seg[2*id], 0, seg[id].low);
seg[2*id] = add(seg[2*id], 1, seg[id].high);
seg[2*id+1] = add(seg[2*id+1], 0, seg[id].low);
seg[2*id+1] = add(seg[2*id+1], 1, seg[id].high);
seg[id].low = 0;
seg[id].high = MAXH;
}
void build(int id = 1, int l = 0, int r = N-1)
{
if(l == r)
{
seg[id].low = seg[id].high = 0;
return;
}
seg[id].low = 0;
seg[id].high = MAXH;
int m = (l+r)/2;
build(2*id, l, m);
build(2*id+1, m+1, r);
}
void update(int x, int y, int type, int val, int id = 1, int l = 0, int r = N-1)
{
//std::cout << x << " " << y << " " << type << ' ' << val << " " << id << ' ' << l << ' ' << r << std::endl;
if(y < l || x > r)
return;
if(x <= l && r <= y)
{
seg[id] = add(seg[id], type, val);
//std::cout << seg[id].low << " " << seg[id].high << std::endl;
return;
}
shift(id);
int m = (l+r)/2;
update(x, y, type, val, 2*id, l, m);
update(x, y, type, val, 2*id+1, m+1, r);
}
int val(int x, int id = 1, int l = 0, int r = N-1)
{
if(l == r)
return seg[id].low;
shift(id);
int m = (l+r)/2;
if(x <= m)
return val(x, 2*id, l, m);
else
return val(x, 2*id+1, m+1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
N = n;
build();
for(int i = 0; i < k; i++)
{
update(left[i], right[i], op[i]-1, height[i]);
}
for(int i = 0; i < n; i++)
{
finalHeight[i] = val(i);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
504 KB |
Output is correct |
3 |
Correct |
4 ms |
376 KB |
Output is correct |
4 |
Correct |
9 ms |
760 KB |
Output is correct |
5 |
Correct |
9 ms |
888 KB |
Output is correct |
6 |
Correct |
8 ms |
760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
177 ms |
13980 KB |
Output is correct |
3 |
Correct |
208 ms |
8056 KB |
Output is correct |
4 |
Correct |
584 ms |
20384 KB |
Output is correct |
5 |
Correct |
366 ms |
21480 KB |
Output is correct |
6 |
Correct |
357 ms |
20008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
504 KB |
Output is correct |
3 |
Correct |
4 ms |
376 KB |
Output is correct |
4 |
Correct |
9 ms |
888 KB |
Output is correct |
5 |
Correct |
9 ms |
760 KB |
Output is correct |
6 |
Correct |
8 ms |
760 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
176 ms |
13944 KB |
Output is correct |
9 |
Correct |
208 ms |
7928 KB |
Output is correct |
10 |
Correct |
588 ms |
20384 KB |
Output is correct |
11 |
Correct |
359 ms |
21564 KB |
Output is correct |
12 |
Correct |
355 ms |
19876 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
179 ms |
14000 KB |
Output is correct |
15 |
Correct |
37 ms |
2040 KB |
Output is correct |
16 |
Correct |
596 ms |
20652 KB |
Output is correct |
17 |
Correct |
363 ms |
20068 KB |
Output is correct |
18 |
Correct |
359 ms |
20140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
504 KB |
Output is correct |
3 |
Correct |
3 ms |
380 KB |
Output is correct |
4 |
Correct |
9 ms |
888 KB |
Output is correct |
5 |
Correct |
8 ms |
888 KB |
Output is correct |
6 |
Correct |
8 ms |
760 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
177 ms |
14120 KB |
Output is correct |
9 |
Correct |
209 ms |
7984 KB |
Output is correct |
10 |
Correct |
589 ms |
20428 KB |
Output is correct |
11 |
Correct |
361 ms |
21496 KB |
Output is correct |
12 |
Correct |
352 ms |
20012 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
186 ms |
13944 KB |
Output is correct |
15 |
Correct |
37 ms |
2040 KB |
Output is correct |
16 |
Correct |
592 ms |
20808 KB |
Output is correct |
17 |
Correct |
415 ms |
20088 KB |
Output is correct |
18 |
Correct |
358 ms |
20248 KB |
Output is correct |
19 |
Correct |
1126 ms |
69608 KB |
Output is correct |
20 |
Correct |
1114 ms |
67192 KB |
Output is correct |
21 |
Correct |
1130 ms |
69692 KB |
Output is correct |
22 |
Correct |
1107 ms |
67000 KB |
Output is correct |
23 |
Correct |
1120 ms |
67096 KB |
Output is correct |
24 |
Correct |
1114 ms |
67108 KB |
Output is correct |
25 |
Correct |
1107 ms |
67100 KB |
Output is correct |
26 |
Correct |
1164 ms |
69724 KB |
Output is correct |
27 |
Correct |
1126 ms |
69624 KB |
Output is correct |
28 |
Correct |
1117 ms |
67320 KB |
Output is correct |
29 |
Correct |
1112 ms |
67140 KB |
Output is correct |
30 |
Correct |
1130 ms |
67008 KB |
Output is correct |