oj.uz

답안 #38866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
38866 2018-01-07T11:56:29 Z 14kg 말 (IOI15_horses) C++11
17 / 100
 183 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, (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));
}

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];
	}

	long long out = ll_mul(get_tree1(1, 1, nn, 1, tree2[1]).num, Y[tree2[1]]);
	return (int)(out%MOD);
}

int updateX(int pos, int val) {	
	return 0;
}

int updateY(int pos, int val) {
	return 0;
}

Compilation message

horses.cpp:58:17: warning: unused parameter 'pos' [-Wunused-parameter]
 int updateX(int pos, int val) { 
                 ^
horses.cpp:58:26: warning: unused parameter 'val' [-Wunused-parameter]
 int updateX(int pos, int val) { 
                          ^
horses.cpp:62:17: warning: unused parameter 'pos' [-Wunused-parameter]
 int updateY(int pos, int val) {
                 ^
horses.cpp:62:26: warning: unused parameter 'val' [-Wunused-parameter]
 int updateY(int pos, int val) {
                          ^

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 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

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 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 Incorrect 0 ms 15356 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 183 ms 19268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 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 Incorrect 0 ms 15356 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 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 Incorrect 0 ms 15356 KB Output isn't correct
22 Halted 0 ms 0 KB -