oj.uz

Submission #39350

# Submission time Handle Problem Language Result Execution time Memory
39350 2018-01-12T05:35:11 Z 14kg Game (IOI13_game) C++11
63 / 100
 3649 ms 256000 KB 
#include "game.h"
#include <algorithm>

using namespace std;
struct NODE {
	long long num;
	NODE *left, *right;
};
struct TREE {
	TREE *left, *right;
	NODE *node_top;
} *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;
	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;
	//printf("    ==== %d %d %d %d / %d %d\n", l, r, x, y, node->left != NULL, node->right != NULL);
	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 (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) {
	// printf("      >>> %lld\n", top->node_top->left->num);
	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) {
	//	printf("(%d %d) - %d   = %lld\n", l, r, p_x, p_num);
		Push_NODE(tree->node_top, 1, m_d, p_x, 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);
//	printf("(%d %d) - %d   = %lld\n", l, r, 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

# Verdict Execution time Memory 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 0 ms 1116 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory 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 843 ms 16428 KB Output is correct
5 Correct 573 ms 16428 KB Output is correct
6 Correct 926 ms 16824 KB Output is correct
7 Correct 1096 ms 16824 KB Output is correct
8 Correct 669 ms 10224 KB Output is correct
9 Correct 1086 ms 16956 KB Output is correct
10 Correct 1026 ms 16824 KB Output is correct
11 Correct 0 ms 1116 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory 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 1369 ms 19200 KB Output is correct
13 Correct 2879 ms 8904 KB Output is correct
14 Correct 589 ms 1248 KB Output is correct
15 Correct 3443 ms 13260 KB Output is correct
16 Correct 576 ms 29496 KB Output is correct
17 Correct 1929 ms 17748 KB Output is correct
18 Correct 3549 ms 29496 KB Output is correct
19 Correct 3366 ms 29628 KB Output is correct
20 Correct 2939 ms 29496 KB Output is correct
21 Correct 0 ms 1116 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory 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 899 ms 16428 KB Output is correct
13 Correct 633 ms 16428 KB Output is correct
14 Correct 973 ms 16824 KB Output is correct
15 Correct 1049 ms 16824 KB Output is correct
16 Correct 673 ms 10224 KB Output is correct
17 Correct 1036 ms 16956 KB Output is correct
18 Correct 1018 ms 16824 KB Output is correct
19 Correct 1439 ms 19200 KB Output is correct
20 Correct 2923 ms 8904 KB Output is correct
21 Correct 473 ms 1248 KB Output is correct
22 Correct 3339 ms 13260 KB Output is correct
23 Correct 629 ms 29496 KB Output is correct
24 Correct 1933 ms 17748 KB Output is correct
25 Correct 3353 ms 29496 KB Output is correct
26 Correct 3086 ms 29628 KB Output is correct
27 Correct 2889 ms 29496 KB Output is correct
28 Memory limit exceeded 816 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory 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 899 ms 16428 KB Output is correct
13 Correct 566 ms 16428 KB Output is correct
14 Correct 959 ms 16824 KB Output is correct
15 Correct 1008 ms 16824 KB Output is correct
16 Correct 733 ms 10224 KB Output is correct
17 Correct 1109 ms 16956 KB Output is correct
18 Correct 916 ms 16824 KB Output is correct
19 Correct 1496 ms 19200 KB Output is correct
20 Correct 2879 ms 8904 KB Output is correct
21 Correct 483 ms 1248 KB Output is correct
22 Correct 3319 ms 13260 KB Output is correct
23 Correct 523 ms 29496 KB Output is correct
24 Correct 1899 ms 17748 KB Output is correct
25 Correct 3649 ms 29496 KB Output is correct
26 Correct 2876 ms 29628 KB Output is correct
27 Correct 2916 ms 29496 KB Output is correct
28 Memory limit exceeded 793 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -