oj.uz

Submission #39355

# Submission time Handle Problem Language Result Execution time Memory
39355 2018-01-12T11:20:35 Z 14kg Game (IOI13_game) C++11
37 / 100
 3099 ms 19332 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) {
	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

# 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 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

# 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 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

# 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 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

# 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 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 -