oj.uz

Submission #39356

# Submission time Handle Problem Language Result Execution time Memory
39356 2018-01-12T11:26:10 Z 14kg Game (IOI13_game) C++11
63 / 100
 4073 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;
	
	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) {
	long long a, b;
	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 ((mid < w || w < l) && tree->left == NULL) a = 0;
	else {
		if (tree->left == NULL) tree->left = make_TREE();
		a = Push_TREE(tree->left, l, mid, w, p_x, p_num);
	}
	if ((r < w || w < mid + 1) && tree->right == NULL) b = 0;
	else {
		if (tree->right == NULL) tree->right = make_TREE();
		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

# 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 916 ms 16428 KB Output is correct
5 Correct 536 ms 16428 KB Output is correct
6 Correct 1069 ms 16824 KB Output is correct
7 Correct 1453 ms 16824 KB Output is correct
8 Correct 786 ms 10224 KB Output is correct
9 Correct 1166 ms 16956 KB Output is correct
10 Correct 1173 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 1433 ms 19332 KB Output is correct
13 Correct 2869 ms 8904 KB Output is correct
14 Correct 446 ms 1248 KB Output is correct
15 Correct 3393 ms 13260 KB Output is correct
16 Correct 606 ms 29628 KB Output is correct
17 Correct 2126 ms 17748 KB Output is correct
18 Correct 4073 ms 29628 KB Output is correct
19 Correct 3279 ms 29628 KB Output is correct
20 Correct 2996 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 939 ms 16428 KB Output is correct
13 Correct 609 ms 16428 KB Output is correct
14 Correct 1229 ms 16824 KB Output is correct
15 Correct 1376 ms 16824 KB Output is correct
16 Correct 806 ms 10224 KB Output is correct
17 Correct 1343 ms 16956 KB Output is correct
18 Correct 1199 ms 16824 KB Output is correct
19 Correct 1476 ms 19332 KB Output is correct
20 Correct 3296 ms 8904 KB Output is correct
21 Correct 536 ms 1248 KB Output is correct
22 Correct 3453 ms 13260 KB Output is correct
23 Correct 559 ms 29628 KB Output is correct
24 Correct 2056 ms 17748 KB Output is correct
25 Correct 3759 ms 29628 KB Output is correct
26 Correct 3103 ms 29628 KB Output is correct
27 Correct 3213 ms 29496 KB Output is correct
28 Memory limit exceeded 833 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 889 ms 16428 KB Output is correct
13 Correct 543 ms 16428 KB Output is correct
14 Correct 1073 ms 16824 KB Output is correct
15 Correct 1236 ms 16824 KB Output is correct
16 Correct 779 ms 10224 KB Output is correct
17 Correct 1216 ms 16956 KB Output is correct
18 Correct 1106 ms 16824 KB Output is correct
19 Correct 1653 ms 19332 KB Output is correct
20 Correct 3106 ms 8904 KB Output is correct
21 Correct 499 ms 1248 KB Output is correct
22 Correct 3413 ms 13260 KB Output is correct
23 Correct 586 ms 29628 KB Output is correct
24 Correct 2309 ms 17748 KB Output is correct
25 Correct 3816 ms 29628 KB Output is correct
26 Correct 3246 ms 29628 KB Output is correct
27 Correct 2853 ms 29496 KB Output is correct
28 Memory limit exceeded 806 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -