답안 #30909

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30909 2017-08-01T03:58:36 Z h0ngjun7 벽 (IOI14_wall) C++14
100 / 100
966 ms 87072 KB
#include "wall.h"
#include <algorithm>
using namespace std;
 
const int MAXN = 2000005;
 
struct SEG {
	int max, min;
} seg[4 * MAXN];
 
int n;
 
void push(int x) {
	int L = x * 2, R = x * 2 + 1;
	seg[L].min = min(max(seg[L].min, seg[x].min), seg[x].max);
	seg[R].min = min(max(seg[R].min, seg[x].min), seg[x].max);
	seg[L].max = max(min(seg[L].max, seg[x].max), seg[x].min);
	seg[R].max = max(min(seg[R].max, seg[x].max), seg[x].min);
}
 
void query(int x, int s, int e, int l, int r, int h, int op) {
	if (s > e) return;
	if (e < l || r < s) return;
	if (l <= s && e <= r) {
		if (op == 1) {
			seg[x].min = max(seg[x].min, h);
			seg[x].max = max(seg[x].max, h);
		}
		else {
			seg[x].max = min(seg[x].max, h);
			seg[x].min = min(seg[x].min, h);
		}
		return;
	}
	if (s < e) {
		int m = (s + e) / 2;
		push(x);
		query(x * 2, s, m, l, r, h, op);
		query(x * 2 + 1, m + 1, e, l, r, h, op);
		seg[x].max = max(seg[x * 2].max, seg[x * 2 + 1].max);
		seg[x].min = min(seg[x * 2].min, seg[x * 2 + 1].min);
	}
}
 
int ans[MAXN];
void dfs(int x, int s, int e) {
	if (s > e) return;
	if (s == e) {
		ans[s] = seg[x].max;
		return;
	}
	push(x);
	int m = (s + e) / 2;
	dfs(x * 2, s, m);
	dfs(x * 2 + 1, m + 1, e);
}
 
void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	n = _n;
	for (int i = 0; i < k; i++) {
		query(1, 0, n - 1, left[i], right[i], height[i], op[i]);
	}
	dfs(1, 0, n - 1);
	for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
	return;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 71432 KB Output is correct
2 Correct 0 ms 71432 KB Output is correct
3 Correct 0 ms 71432 KB Output is correct
4 Correct 3 ms 71432 KB Output is correct
5 Correct 6 ms 71432 KB Output is correct
6 Correct 6 ms 71432 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 71432 KB Output is correct
2 Correct 213 ms 79256 KB Output is correct
3 Correct 249 ms 74680 KB Output is correct
4 Correct 763 ms 79648 KB Output is correct
5 Correct 459 ms 79648 KB Output is correct
6 Correct 393 ms 79648 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 71432 KB Output is correct
2 Correct 0 ms 71432 KB Output is correct
3 Correct 0 ms 71432 KB Output is correct
4 Correct 6 ms 71432 KB Output is correct
5 Correct 6 ms 71432 KB Output is correct
6 Correct 6 ms 71432 KB Output is correct
7 Correct 0 ms 71432 KB Output is correct
8 Correct 199 ms 79256 KB Output is correct
9 Correct 203 ms 74680 KB Output is correct
10 Correct 716 ms 79648 KB Output is correct
11 Correct 419 ms 79648 KB Output is correct
12 Correct 429 ms 79648 KB Output is correct
13 Correct 0 ms 71432 KB Output is correct
14 Correct 213 ms 79256 KB Output is correct
15 Correct 46 ms 71920 KB Output is correct
16 Correct 666 ms 79648 KB Output is correct
17 Correct 426 ms 79648 KB Output is correct
18 Correct 473 ms 79648 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 71432 KB Output is correct
2 Correct 0 ms 71432 KB Output is correct
3 Correct 0 ms 71432 KB Output is correct
4 Correct 9 ms 71432 KB Output is correct
5 Correct 6 ms 71432 KB Output is correct
6 Correct 6 ms 71432 KB Output is correct
7 Correct 0 ms 71432 KB Output is correct
8 Correct 173 ms 79256 KB Output is correct
9 Correct 256 ms 74680 KB Output is correct
10 Correct 783 ms 79648 KB Output is correct
11 Correct 409 ms 79648 KB Output is correct
12 Correct 456 ms 79648 KB Output is correct
13 Correct 0 ms 71432 KB Output is correct
14 Correct 233 ms 79256 KB Output is correct
15 Correct 39 ms 71920 KB Output is correct
16 Correct 643 ms 79648 KB Output is correct
17 Correct 393 ms 79648 KB Output is correct
18 Correct 396 ms 79648 KB Output is correct
19 Correct 956 ms 87072 KB Output is correct
20 Correct 966 ms 87072 KB Output is correct
21 Correct 966 ms 87072 KB Output is correct
22 Correct 946 ms 87072 KB Output is correct
23 Correct 836 ms 87072 KB Output is correct
24 Correct 876 ms 87072 KB Output is correct
25 Correct 959 ms 87072 KB Output is correct
26 Correct 866 ms 87072 KB Output is correct
27 Correct 866 ms 87072 KB Output is correct
28 Correct 859 ms 87072 KB Output is correct
29 Correct 899 ms 87072 KB Output is correct
30 Correct 926 ms 87072 KB Output is correct