oj.uz

답안 #232339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232339 2020-05-16T19:04:45 Z islingr 벽 (IOI14_wall) C++14
100 / 100
 692 ms 59240 KB 
#include <iostream>
using namespace std;

const int inf = 1e9, N = 1 << 22;
int mx[N], mn[N];

void change(int v, int d, int u) {
	mn[v] = max(u, min(d, mn[v]));
	mx[v] = min(d, max(u, mx[v]));
}

void push(int v) {
	change(v << 1|0, mn[v], mx[v]);
	change(v << 1|1, mn[v], mx[v]);
	mx[v] = 0; mn[v] = inf;
}

int d, u, lo, hi;
void update(int v, int l, int r) {
	if (hi <= l || r <= lo) return;
	if (lo <= l && r <= hi) return change(v, d, u);
	push(v); int m = (l + r) / 2;
	update(v << 1|0, l, m);
	update(v << 1|1, m, r);
}

void final(int ans[], int v, int l, int r) {
	if (r - l == 1)
		return void(ans[l] = min(mx[v], mn[v]));
	push(v); int m = (l + r) / 2;
	final(ans, v << 1|0, l, m);
	final(ans, v << 1|1, m, r);
}

void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ans[]) {
	for (int i = 0; i < N; ++i) mn[i] = inf, mx[i] = 0;
	for (int i = 0; i < q; ++i) {
		lo = l[i]; hi = r[i] + 1;
		d = op[i] != 1 ? h[i] : inf;
		u = op[i] != 1 ? 0 : h[i];
		update(1, 0, n);
	}
	final(ans, 1, 0, n);
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 33152 KB Output is correct
2 Correct 25 ms 33280 KB Output is correct
3 Correct 23 ms 33152 KB Output is correct
4 Correct 27 ms 33280 KB Output is correct
5 Correct 26 ms 33280 KB Output is correct
6 Correct 26 ms 33408 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 33280 KB Output is correct
2 Correct 190 ms 40952 KB Output is correct
3 Correct 194 ms 36472 KB Output is correct
4 Correct 505 ms 41720 KB Output is correct
5 Correct 318 ms 42104 KB Output is correct
6 Correct 307 ms 42232 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 33152 KB Output is correct
2 Correct 24 ms 33280 KB Output is correct
3 Correct 23 ms 33152 KB Output is correct
4 Correct 27 ms 33280 KB Output is correct
5 Correct 27 ms 33280 KB Output is correct
6 Correct 27 ms 33280 KB Output is correct
7 Correct 22 ms 33152 KB Output is correct
8 Correct 186 ms 40952 KB Output is correct
9 Correct 189 ms 36472 KB Output is correct
10 Correct 487 ms 41592 KB Output is correct
11 Correct 317 ms 42104 KB Output is correct
12 Correct 315 ms 42232 KB Output is correct
13 Correct 22 ms 33152 KB Output is correct
14 Correct 190 ms 41080 KB Output is correct
15 Correct 49 ms 33784 KB Output is correct
16 Correct 473 ms 41824 KB Output is correct
17 Correct 323 ms 41848 KB Output is correct
18 Correct 325 ms 41816 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 33152 KB Output is correct
2 Correct 23 ms 33272 KB Output is correct
3 Correct 24 ms 33280 KB Output is correct
4 Correct 27 ms 33280 KB Output is correct
5 Correct 28 ms 33280 KB Output is correct
6 Correct 26 ms 33280 KB Output is correct
7 Correct 23 ms 33144 KB Output is correct
8 Correct 187 ms 40952 KB Output is correct
9 Correct 195 ms 36600 KB Output is correct
10 Correct 476 ms 41592 KB Output is correct
11 Correct 318 ms 42136 KB Output is correct
12 Correct 308 ms 42104 KB Output is correct
13 Correct 22 ms 33152 KB Output is correct
14 Correct 188 ms 41044 KB Output is correct
15 Correct 49 ms 33788 KB Output is correct
16 Correct 486 ms 41848 KB Output is correct
17 Correct 323 ms 41848 KB Output is correct
18 Correct 316 ms 41976 KB Output is correct
19 Correct 680 ms 59240 KB Output is correct
20 Correct 686 ms 56800 KB Output is correct
21 Correct 679 ms 59208 KB Output is correct
22 Correct 676 ms 56552 KB Output is correct
23 Correct 683 ms 56764 KB Output is correct
24 Correct 673 ms 56676 KB Output is correct
25 Correct 670 ms 56540 KB Output is correct
26 Correct 677 ms 59228 KB Output is correct
27 Correct 670 ms 59128 KB Output is correct
28 Correct 678 ms 56576 KB Output is correct
29 Correct 674 ms 56696 KB Output is correct
30 Correct 692 ms 56696 KB Output is correct