oj.uz

Submission #39353

# Submission time Handle Problem Language Result Execution time Memory
39353 2018-01-12T10:41:05 Z 14kg Game (IOI13_game) C++11
63 / 100
 4309 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 (x <= l && r <= y) return get_NODE(tree->node_top, 1, m_d, p_x, p_y);
	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 (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

# 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 546 ms 16428 KB Output is correct
6 Correct 1079 ms 16824 KB Output is correct
7 Correct 1273 ms 16824 KB Output is correct
8 Correct 773 ms 10224 KB Output is correct
9 Correct 1296 ms 16956 KB Output is correct
10 Correct 1006 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 1476 ms 19332 KB Output is correct
13 Correct 2926 ms 8904 KB Output is correct
14 Correct 503 ms 1248 KB Output is correct
15 Correct 3453 ms 13260 KB Output is correct
16 Correct 579 ms 29628 KB Output is correct
17 Correct 2183 ms 17748 KB Output is correct
18 Correct 3596 ms 29628 KB Output is correct
19 Correct 3113 ms 29628 KB Output is correct
20 Correct 3069 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 873 ms 16428 KB Output is correct
13 Correct 589 ms 16428 KB Output is correct
14 Correct 1073 ms 16824 KB Output is correct
15 Correct 1313 ms 16824 KB Output is correct
16 Correct 706 ms 10224 KB Output is correct
17 Correct 1213 ms 16956 KB Output is correct
18 Correct 1039 ms 16824 KB Output is correct
19 Correct 1556 ms 19332 KB Output is correct
20 Correct 3063 ms 8904 KB Output is correct
21 Correct 513 ms 1248 KB Output is correct
22 Correct 3576 ms 13260 KB Output is correct
23 Correct 589 ms 29628 KB Output is correct
24 Correct 2516 ms 17748 KB Output is correct
25 Correct 4309 ms 29628 KB Output is correct
26 Correct 3159 ms 29628 KB Output is correct
27 Correct 3129 ms 29496 KB Output is correct
28 Memory limit exceeded 903 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 906 ms 16428 KB Output is correct
13 Correct 636 ms 16428 KB Output is correct
14 Correct 993 ms 16824 KB Output is correct
15 Correct 1359 ms 16824 KB Output is correct
16 Correct 733 ms 10224 KB Output is correct
17 Correct 1209 ms 16956 KB Output is correct
18 Correct 1089 ms 16824 KB Output is correct
19 Correct 1499 ms 19332 KB Output is correct
20 Correct 2856 ms 8904 KB Output is correct
21 Correct 446 ms 1248 KB Output is correct
22 Correct 3429 ms 13260 KB Output is correct
23 Correct 583 ms 29628 KB Output is correct
24 Correct 2293 ms 17748 KB Output is correct
25 Correct 4043 ms 29628 KB Output is correct
26 Correct 2926 ms 29628 KB Output is correct
27 Correct 2896 ms 29496 KB Output is correct
28 Memory limit exceeded 873 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -