답안 #38868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
38868 2018-01-07T12:31:12 Z 14kg 말 (IOI15_horses) C++11
100 / 100
1363 ms 19268 KB
#include "horses.h"
#define MOD 1000000007
#define N 500001
#define NN 1048576

struct NUM {
	bool big_num;
	int num;
	void push(bool _big_num, int _num) {
		big_num = _big_num, num = _num;
	}
} tree1[NN], one;
int n, nn, tree2[NN], Y[N];

NUM mul(NUM x, NUM y) {
	long long tx = x.num, ty = y.num, temp = (tx*ty) % MOD;
	NUM res;

	res.push(tx*ty >= MOD || x.big_num || y.big_num, (int)temp);
	return res;
}
long long ll_mul(long long x, long long y) {
	return x*y;
}

NUM get_tree1(int lev, int l, int r, int x, int y) {
	int mid = (l + r) / 2;

	if (x <= l && r <= y) return tree1[lev];
	if (r < x || y < l) return one;
	return mul(get_tree1(lev * 2, l, mid, x, y), get_tree1(lev * 2 + 1, mid + 1, r, x, y));
}
void tree1_update(int lev) {
	tree1[lev] = mul(tree1[lev * 2], tree1[lev * 2 + 1]);

	if (lev > 1) tree1_update(lev / 2);
}
void tree2_update(int lev) {
	int l = lev * 2, r = lev * 2 + 1;
	NUM temp = get_tree1(1, 1, nn, tree2[l] + 1, tree2[r]);

	if (temp.big_num || (long long)Y[tree2[l]] <= ll_mul(temp.num, Y[tree2[r]])) tree2[lev] = tree2[r];
	else tree2[lev] = tree2[l];

	if (lev > 1) tree2_update(lev / 2);
}
int output() {
	long long out = ll_mul(get_tree1(1, 1, nn, 1, tree2[1]).num, Y[tree2[1]]);
	return (int)(out%MOD);
}

int init(int _n, int *in_x, int *in_y) {
	NUM temp;

	n = _n, one.push(false, 1);
	for (nn = 1; nn < n; nn *= 2);
	for (int i = 0; i < n; i++) {
		tree1[nn + i].push(false, in_x[i]);
		tree2[nn + i] = i + 1;
		Y[i + 1] = in_y[i];
	}

	for (int i = nn - 1; i >= 1; i--) tree1[i] = mul(tree1[i * 2], tree1[i * 2 + 1]);
	for (int i = nn - 1; i >= 1; i--) {
		int l = i * 2, r = i * 2 + 1;
		temp = get_tree1(1, 1, nn, tree2[l] + 1, tree2[r]);

		if (temp.big_num || (long long)Y[tree2[l]] <= ll_mul(temp.num, Y[tree2[r]])) tree2[i] = tree2[r];
		else tree2[i] = tree2[l];
	}

	return output();
}
int updateX(int pos, int val) {	
	tree1[nn + pos].push(false, val);
	tree1_update((nn + pos) / 2), tree2_update((nn + pos) / 2);
	return output();
}
int updateY(int pos, int val) {
	Y[pos + 1] = val;
	tree2_update((nn + pos) / 2);
	return output();
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 15356 KB Output is correct
2 Correct 0 ms 15356 KB Output is correct
3 Correct 0 ms 15356 KB Output is correct
4 Correct 0 ms 15356 KB Output is correct
5 Correct 0 ms 15356 KB Output is correct
6 Correct 0 ms 15356 KB Output is correct
7 Correct 0 ms 15356 KB Output is correct
8 Correct 0 ms 15356 KB Output is correct
9 Correct 0 ms 15356 KB Output is correct
10 Correct 0 ms 15356 KB Output is correct
11 Correct 0 ms 15356 KB Output is correct
12 Correct 0 ms 15356 KB Output is correct
13 Correct 0 ms 15356 KB Output is correct
14 Correct 0 ms 15356 KB Output is correct
15 Correct 0 ms 15356 KB Output is correct
16 Correct 0 ms 15356 KB Output is correct
17 Correct 0 ms 15356 KB Output is correct
18 Correct 0 ms 15356 KB Output is correct
19 Correct 0 ms 15356 KB Output is correct
20 Correct 0 ms 15356 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 15356 KB Output is correct
2 Correct 0 ms 15356 KB Output is correct
3 Correct 0 ms 15356 KB Output is correct
4 Correct 0 ms 15356 KB Output is correct
5 Correct 0 ms 15356 KB Output is correct
6 Correct 0 ms 15356 KB Output is correct
7 Correct 0 ms 15356 KB Output is correct
8 Correct 0 ms 15356 KB Output is correct
9 Correct 0 ms 15356 KB Output is correct
10 Correct 0 ms 15356 KB Output is correct
11 Correct 0 ms 15356 KB Output is correct
12 Correct 0 ms 15356 KB Output is correct
13 Correct 0 ms 15356 KB Output is correct
14 Correct 0 ms 15356 KB Output is correct
15 Correct 0 ms 15356 KB Output is correct
16 Correct 0 ms 15356 KB Output is correct
17 Correct 0 ms 15356 KB Output is correct
18 Correct 0 ms 15356 KB Output is correct
19 Correct 0 ms 15356 KB Output is correct
20 Correct 0 ms 15356 KB Output is correct
21 Correct 0 ms 15356 KB Output is correct
22 Correct 0 ms 15356 KB Output is correct
23 Correct 3 ms 15356 KB Output is correct
24 Correct 0 ms 15356 KB Output is correct
25 Correct 0 ms 15356 KB Output is correct
26 Correct 0 ms 15356 KB Output is correct
27 Correct 0 ms 15356 KB Output is correct
28 Correct 0 ms 15356 KB Output is correct
29 Correct 0 ms 15356 KB Output is correct
30 Correct 0 ms 15356 KB Output is correct
31 Correct 0 ms 15356 KB Output is correct
32 Correct 0 ms 15356 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 526 ms 19268 KB Output is correct
2 Correct 796 ms 19268 KB Output is correct
3 Correct 946 ms 19268 KB Output is correct
4 Correct 946 ms 19268 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 15356 KB Output is correct
2 Correct 0 ms 15356 KB Output is correct
3 Correct 0 ms 15356 KB Output is correct
4 Correct 0 ms 15356 KB Output is correct
5 Correct 0 ms 15356 KB Output is correct
6 Correct 0 ms 15356 KB Output is correct
7 Correct 0 ms 15356 KB Output is correct
8 Correct 0 ms 15356 KB Output is correct
9 Correct 0 ms 15356 KB Output is correct
10 Correct 0 ms 15356 KB Output is correct
11 Correct 0 ms 15356 KB Output is correct
12 Correct 0 ms 15356 KB Output is correct
13 Correct 0 ms 15356 KB Output is correct
14 Correct 0 ms 15356 KB Output is correct
15 Correct 0 ms 15356 KB Output is correct
16 Correct 0 ms 15356 KB Output is correct
17 Correct 0 ms 15356 KB Output is correct
18 Correct 0 ms 15356 KB Output is correct
19 Correct 0 ms 15356 KB Output is correct
20 Correct 0 ms 15356 KB Output is correct
21 Correct 0 ms 15356 KB Output is correct
22 Correct 0 ms 15356 KB Output is correct
23 Correct 0 ms 15356 KB Output is correct
24 Correct 3 ms 15356 KB Output is correct
25 Correct 3 ms 15356 KB Output is correct
26 Correct 0 ms 15356 KB Output is correct
27 Correct 0 ms 15356 KB Output is correct
28 Correct 3 ms 15356 KB Output is correct
29 Correct 0 ms 15356 KB Output is correct
30 Correct 0 ms 15356 KB Output is correct
31 Correct 3 ms 15356 KB Output is correct
32 Correct 0 ms 15356 KB Output is correct
33 Correct 323 ms 19268 KB Output is correct
34 Correct 363 ms 19268 KB Output is correct
35 Correct 243 ms 19268 KB Output is correct
36 Correct 229 ms 19268 KB Output is correct
37 Correct 266 ms 19268 KB Output is correct
38 Correct 213 ms 19268 KB Output is correct
39 Correct 176 ms 19268 KB Output is correct
40 Correct 213 ms 19268 KB Output is correct
41 Correct 239 ms 19268 KB Output is correct
42 Correct 203 ms 19268 KB Output is correct
43 Correct 173 ms 19268 KB Output is correct
44 Correct 193 ms 19268 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 15356 KB Output is correct
2 Correct 0 ms 15356 KB Output is correct
3 Correct 0 ms 15356 KB Output is correct
4 Correct 0 ms 15356 KB Output is correct
5 Correct 0 ms 15356 KB Output is correct
6 Correct 0 ms 15356 KB Output is correct
7 Correct 0 ms 15356 KB Output is correct
8 Correct 0 ms 15356 KB Output is correct
9 Correct 0 ms 15356 KB Output is correct
10 Correct 0 ms 15356 KB Output is correct
11 Correct 0 ms 15356 KB Output is correct
12 Correct 0 ms 15356 KB Output is correct
13 Correct 0 ms 15356 KB Output is correct
14 Correct 0 ms 15356 KB Output is correct
15 Correct 0 ms 15356 KB Output is correct
16 Correct 0 ms 15356 KB Output is correct
17 Correct 0 ms 15356 KB Output is correct
18 Correct 0 ms 15356 KB Output is correct
19 Correct 0 ms 15356 KB Output is correct
20 Correct 0 ms 15356 KB Output is correct
21 Correct 0 ms 15356 KB Output is correct
22 Correct 0 ms 15356 KB Output is correct
23 Correct 3 ms 15356 KB Output is correct
24 Correct 3 ms 15356 KB Output is correct
25 Correct 0 ms 15356 KB Output is correct
26 Correct 0 ms 15356 KB Output is correct
27 Correct 3 ms 15356 KB Output is correct
28 Correct 0 ms 15356 KB Output is correct
29 Correct 0 ms 15356 KB Output is correct
30 Correct 0 ms 15356 KB Output is correct
31 Correct 0 ms 15356 KB Output is correct
32 Correct 0 ms 15356 KB Output is correct
33 Correct 549 ms 19268 KB Output is correct
34 Correct 713 ms 19268 KB Output is correct
35 Correct 996 ms 19268 KB Output is correct
36 Correct 899 ms 19268 KB Output is correct
37 Correct 309 ms 19268 KB Output is correct
38 Correct 316 ms 19268 KB Output is correct
39 Correct 229 ms 19268 KB Output is correct
40 Correct 223 ms 19268 KB Output is correct
41 Correct 253 ms 19268 KB Output is correct
42 Correct 233 ms 19268 KB Output is correct
43 Correct 189 ms 19268 KB Output is correct
44 Correct 203 ms 19268 KB Output is correct
45 Correct 199 ms 19268 KB Output is correct
46 Correct 196 ms 19268 KB Output is correct
47 Correct 199 ms 19268 KB Output is correct
48 Correct 159 ms 19268 KB Output is correct
49 Correct 1306 ms 19268 KB Output is correct
50 Correct 1363 ms 19268 KB Output is correct
51 Correct 583 ms 19268 KB Output is correct
52 Correct 569 ms 19268 KB Output is correct
53 Correct 1129 ms 19268 KB Output is correct
54 Correct 636 ms 19268 KB Output is correct
55 Correct 486 ms 19268 KB Output is correct
56 Correct 546 ms 19268 KB Output is correct
57 Correct 739 ms 19268 KB Output is correct
58 Correct 613 ms 19268 KB Output is correct
59 Correct 176 ms 19268 KB Output is correct