답안 #39354 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39354	2018-01-12T11:12:21 Z	14kg	게임 (IOI13_game)	C++11	37 / 100	2976 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->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	856 ms	16428 KB	Output is correct
5	Correct	599 ms	16428 KB	Output is correct
6	Correct	1026 ms	16824 KB	Output is correct
7	Correct	1246 ms	16824 KB	Output is correct
8	Correct	793 ms	10224 KB	Output is correct
9	Correct	1096 ms	16956 KB	Output is correct
10	Correct	1213 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	1463 ms	19332 KB	Output is correct
13	Incorrect	2833 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	903 ms	16428 KB	Output is correct
13	Correct	553 ms	16428 KB	Output is correct
14	Correct	983 ms	16824 KB	Output is correct
15	Correct	1189 ms	16824 KB	Output is correct
16	Correct	639 ms	10224 KB	Output is correct
17	Correct	1046 ms	16956 KB	Output is correct
18	Correct	976 ms	16824 KB	Output is correct
19	Correct	1309 ms	19332 KB	Output is correct
20	Incorrect	2756 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	876 ms	16428 KB	Output is correct
13	Correct	523 ms	16428 KB	Output is correct
14	Correct	1012 ms	16824 KB	Output is correct
15	Correct	1096 ms	16824 KB	Output is correct
16	Correct	739 ms	10224 KB	Output is correct
17	Correct	1206 ms	16956 KB	Output is correct
18	Correct	1029 ms	16824 KB	Output is correct
19	Correct	1419 ms	19332 KB	Output is correct
20	Incorrect	2976 ms	8904 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

답안 #39354

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