답안 #39355 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39355	2018-01-12T11:20:35 Z	14kg	게임 (IOI13_game)	C++11	37 / 100	3099 ms	19332 KB

game

#include "game.h"
#include <algorithm>

using namespace std;
struct NODE {
	long long num;
	NODE *left, *right;
};
struct TREE {
	TREE *left, *right;
	NODE *node_top;
	
	int t_w, t_x;
	long long t_num;
} *top;
int n, n_d, m, m_d;

long long gcd(long long x, long long y) {
	long long tmp;
	while (x != y && y != 0) {
		tmp = x, x = y, y = tmp % y;
	} return x;
}
NODE* make_NODE() {
	NODE *temp = (NODE*)malloc(sizeof(NODE));
	temp->num = 0, temp->left = temp->right = NULL;
	return temp;
}
TREE* make_TREE() {
	TREE *temp = (TREE*)malloc(sizeof(TREE));
	temp->node_top = make_NODE();
	temp->left = temp->right = NULL;
	temp->t_w = -1;
	return temp;
}

void init(int _n, int _m) {
	n = _n, m = _m;
	for (n_d = 1; n_d < n; n_d *= 2);
	for (m_d = 1; m_d < m; m_d *= 2);
	top = make_TREE();
}

long long get_NODE(NODE *node, int l, int r, int x, int y) {
	int mid = (l + r) / 2;
	long long res_l = 0, res_r = 0;

	if (r < x || y < l) return 0;
	if (x <= l && r <= y) return node->num;

	if (node->left != NULL) res_l = get_NODE(node->left, l, mid, x, y);
	if (node->right != NULL) res_r = get_NODE(node->right, mid + 1, r, x, y);
	return gcd(res_l, res_r);
}
long long get_TREE(TREE *tree, int l, int r, int x, int y, int p_x, int p_y) {
	int mid = (l + r) / 2;
	long long res_l = 0, res_r = 0;

	if (r < x || y < l) return 0;
	if (tree->t_w > 0) return (x <= tree->t_w && tree->t_w <= y && p_x <= tree->t_x && tree->t_x <= p_y) ? tree->t_num : 0;
	if (x <= l && r <= y) return get_NODE(tree->node_top, 1, m_d, p_x, p_y);

	if (tree->left != NULL) res_l = get_TREE(tree->left, l, mid, x, y, p_x, p_y);
	if (tree->right != NULL) res_r = get_TREE(tree->right, mid + 1, r, x, y, p_x, p_y);
	return gcd(res_l, res_r);
}
long long calculate(int y_l, int x_l, int y_r, int x_r) {
	return get_TREE(top, 1, n_d, y_l + 1, y_r + 1, x_l + 1, x_r + 1);
}

void Push_NODE(NODE *node, int l, int r, int w, long long num) {
	int mid = (l + r) / 2;

	if (r < w || w < l) return;
	if (l == w && r == w) { node->num = num; return; }

	if (node->left == NULL) node->left = make_NODE();
	if (node->right == NULL) node->right = make_NODE();
	Push_NODE(node->left, l, mid, w, num);
	Push_NODE(node->right, mid + 1, r, w, num);

	node->num = gcd(node->left->num, node->right->num);
}
long long Push_TREE(TREE *tree, int l, int r, int w, int p_x, long long p_num) {
	int mid = (l + r) / 2;

	if (r < w || w < l) return get_NODE(tree->node_top, 1, m_d, p_x, p_x);
	if (l == w && r == w) {
		Push_NODE(tree->node_top, 1, m_d, p_x, p_num);
		return p_num;
	}

	if (tree->t_w>0) {
		int t_w = tree->t_w;
		tree->t_w = -2, Push_TREE(tree, l, r, t_w, tree->t_x, tree->t_num);
		tree->t_w = -1;
	}
	if (tree->t_w != -2 && tree->left == NULL && tree->right == NULL && tree->node_top->num == 0) {
		tree->t_w = w, tree->t_x = p_x, tree->t_num = p_num;
		return p_num;
	}

	if (tree->left == NULL) tree->left = make_TREE();
	if (tree->right == NULL) tree->right = make_TREE();
	long long a = Push_TREE(tree->left, l, mid, w, p_x, p_num);
	long long b = Push_TREE(tree->right, mid + 1, r, w, p_x, p_num);
	long long Push_num = gcd(a, b);

	Push_NODE(tree->node_top, 1, m_d, p_x, Push_num);
	return Push_num;
}
void update(int y, int x, long long num) {
	Push_TREE(top, 1, n_d, y + 1, x + 1, num);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^

Subtask #1
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	1116 KB	Output is correct
2	Correct	1248 KB	Output is correct
3	Correct	1248 KB	Output is correct
4	Correct	1116 KB	Output is correct
5	Correct	1116 KB	Output is correct
6	Correct	1248 KB	Output is correct
7	Correct	1116 KB	Output is correct
8	Correct	1116 KB	Output is correct
9	Correct	1248 KB	Output is correct
10	Correct	1116 KB	Output is correct
11	Correct	1116 KB	Output is correct
12	Correct	1116 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1116 KB	Output is correct
2	Correct	0 ms	1116 KB	Output is correct
3	Correct	0 ms	1116 KB	Output is correct
4	Correct	886 ms	16428 KB	Output is correct
5	Correct	569 ms	16428 KB	Output is correct
6	Correct	1063 ms	16824 KB	Output is correct
7	Correct	1246 ms	16824 KB	Output is correct
8	Correct	686 ms	10224 KB	Output is correct
9	Correct	1089 ms	16956 KB	Output is correct
10	Correct	1116 ms	16824 KB	Output is correct
11	Correct	0 ms	1116 KB	Output is correct

Subtask #3
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1116 KB	Output is correct
2	Correct	0 ms	1248 KB	Output is correct
3	Correct	0 ms	1248 KB	Output is correct
4	Correct	0 ms	1116 KB	Output is correct
5	Correct	0 ms	1116 KB	Output is correct
6	Correct	0 ms	1248 KB	Output is correct
7	Correct	0 ms	1116 KB	Output is correct
8	Correct	0 ms	1116 KB	Output is correct
9	Correct	0 ms	1248 KB	Output is correct
10	Correct	0 ms	1116 KB	Output is correct
11	Correct	0 ms	1116 KB	Output is correct
12	Correct	1393 ms	19332 KB	Output is correct
13	Incorrect	2906 ms	8904 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1116 KB	Output is correct
2	Correct	0 ms	1248 KB	Output is correct
3	Correct	0 ms	1248 KB	Output is correct
4	Correct	0 ms	1116 KB	Output is correct
5	Correct	0 ms	1116 KB	Output is correct
6	Correct	0 ms	1248 KB	Output is correct
7	Correct	0 ms	1116 KB	Output is correct
8	Correct	0 ms	1116 KB	Output is correct
9	Correct	0 ms	1248 KB	Output is correct
10	Correct	0 ms	1116 KB	Output is correct
11	Correct	0 ms	1116 KB	Output is correct
12	Correct	896 ms	16428 KB	Output is correct
13	Correct	556 ms	16428 KB	Output is correct
14	Correct	1069 ms	16824 KB	Output is correct
15	Correct	1249 ms	16824 KB	Output is correct
16	Correct	839 ms	10224 KB	Output is correct
17	Correct	1226 ms	16956 KB	Output is correct
18	Correct	1133 ms	16824 KB	Output is correct
19	Correct	1586 ms	19332 KB	Output is correct
20	Incorrect	3099 ms	8904 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1116 KB	Output is correct
2	Correct	0 ms	1248 KB	Output is correct
3	Correct	0 ms	1248 KB	Output is correct
4	Correct	0 ms	1116 KB	Output is correct
5	Correct	0 ms	1116 KB	Output is correct
6	Correct	0 ms	1248 KB	Output is correct
7	Correct	0 ms	1116 KB	Output is correct
8	Correct	0 ms	1116 KB	Output is correct
9	Correct	0 ms	1248 KB	Output is correct
10	Correct	0 ms	1116 KB	Output is correct
11	Correct	0 ms	1116 KB	Output is correct
12	Correct	909 ms	16428 KB	Output is correct
13	Correct	613 ms	16428 KB	Output is correct
14	Correct	1006 ms	16824 KB	Output is correct
15	Correct	1243 ms	16824 KB	Output is correct
16	Correct	703 ms	10224 KB	Output is correct
17	Correct	1113 ms	16956 KB	Output is correct
18	Correct	936 ms	16824 KB	Output is correct
19	Correct	1463 ms	19332 KB	Output is correct
20	Incorrect	2863 ms	8904 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

답안 #39355

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0