oj.uz

Submission #1090844

# Submission time Handle Problem Language Result Execution time Memory
1090844 2024-09-18T22:22:10 Z LeonidCuk Game (IOI13_game) C++17
100 / 100
 1881 ms 81988 KB 
#include "game.h"
#include <stdlib.h>

typedef long long ll;

static int R, C;

struct X_NODE {
	X_NODE(int s, int e) : s(s), e(e), left(NULL), right(NULL), value(0LL) {}
	int s, e;
	X_NODE *left, *right;
	ll value;
};

struct Y_NODE {
	Y_NODE() : left(NULL), right(NULL), xtree(1, C) {}
	Y_NODE *left, *right;
	X_NODE xtree;
} *root;

ll gcd2(ll x, ll y) {
	if (y == 0) return x;
	return gcd2(y, x % y);
}

void init(int r, int c) {
	R = r, C = c;
	root = new Y_NODE();
}

void update2(X_NODE *node, int q, ll k) {
	int s = node->s, e = node->e, m = (s + e) >> 1;
	if (s == e) {
		node->value = k;
		return;
	}
	X_NODE **child = &(q <= m ? node->left : node->right);
	if (*child == NULL) {
		*child = new X_NODE(q, q);
		(*child)->value = k;
	} else if ((*child)->s <= q && q <= (*child)->e) {
		update2(*child, q, k);
	} else {
		do {
			if (q <= m) e = m;
			else s = m + 1;
			m = (s + e) >> 1;
		} while ((q <= m) == ((*child)->e <= m));
		X_NODE *nnode = new X_NODE(s, e);
		if ((*child)->e <= m) nnode->left = *child;
		else nnode->right = *child;
		*child = nnode;
		update2(*child, q, k);
	}
	node->value =
	    gcd2(node->left ? node->left->value : 0, node->right ? node->right->value : 0);
}

ll query2(X_NODE *node, int s, int e) {
	if (node == NULL || node->s > e || node->e < s) return 0;
	if (s <= node->s && node->e <= e) { return node->value; }
	return gcd2(query2(node->left, s, e), query2(node->right, s, e));
}

void update1(Y_NODE *node, int s, int e, int p, int q, ll k) {
	int m = (s + e) >> 1;
	if (s == e) {
		update2(&node->xtree, q, k);
		return;
	}
	if (p <= m) {
		if (node->left == NULL) node->left = new Y_NODE();
		update1(node->left, s, m, p, q, k);
	} else {
		if (node->right == NULL) node->right = new Y_NODE();
		update1(node->right, m + 1, e, p, q, k);
	}
	ll v = gcd2(node->left ? query2(&node->left->xtree, q, q) : 0,
	            node->right ? query2(&node->right->xtree, q, q) : 0);
	update2(&node->xtree, q, v);
}

void update(int p, int q, ll k) {
	++p, ++q;
	update1(root, 1, R, p, q, k);
}

ll query1(Y_NODE *node, int s, int e, int p, int q, int u, int v) {
	if (node == NULL || s > u || e < p) return 0;
	if (p <= s && e <= u) return query2(&node->xtree, q, v);
	int m = (s + e) >> 1;
	return gcd2(query1(node->left, s, m, p, q, u, v),
	            query1(node->right, m + 1, e, p, q, u, v));
}

ll calculate(int p, int q, int u, int v) {
	++p, ++q, ++u, ++v;
	return query1(root, 1, R, p, q, u, v);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 356 KB Output is correct
7 Correct 0 ms 356 KB Output is correct
8 Correct 0 ms 356 KB Output is correct
9 Correct 0 ms 356 KB Output is correct
10 Correct 0 ms 356 KB Output is correct
11 Correct 0 ms 356 KB Output is correct
12 Correct 0 ms 356 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 317 ms 12964 KB Output is correct
5 Correct 201 ms 12636 KB Output is correct
6 Correct 288 ms 10116 KB Output is correct
7 Correct 325 ms 9844 KB Output is correct
8 Correct 203 ms 8088 KB Output is correct
9 Correct 313 ms 10080 KB Output is correct
10 Correct 298 ms 9588 KB Output is correct
11 Correct 0 ms 360 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 517 ms 15596 KB Output is correct
13 Correct 919 ms 8936 KB Output is correct
14 Correct 162 ms 5716 KB Output is correct
15 Correct 989 ms 10604 KB Output is correct
16 Correct 124 ms 14164 KB Output is correct
17 Correct 481 ms 11144 KB Output is correct
18 Correct 776 ms 15444 KB Output is correct
19 Correct 672 ms 15704 KB Output is correct
20 Correct 602 ms 15160 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 616 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 306 ms 12760 KB Output is correct
13 Correct 202 ms 12620 KB Output is correct
14 Correct 276 ms 10064 KB Output is correct
15 Correct 330 ms 9808 KB Output is correct
16 Correct 201 ms 8084 KB Output is correct
17 Correct 315 ms 9876 KB Output is correct
18 Correct 282 ms 9556 KB Output is correct
19 Correct 533 ms 15700 KB Output is correct
20 Correct 877 ms 8788 KB Output is correct
21 Correct 149 ms 5716 KB Output is correct
22 Correct 1014 ms 10576 KB Output is correct
23 Correct 126 ms 14160 KB Output is correct
24 Correct 455 ms 11088 KB Output is correct
25 Correct 778 ms 15580 KB Output is correct
26 Correct 652 ms 15732 KB Output is correct
27 Correct 617 ms 15060 KB Output is correct
28 Correct 270 ms 43220 KB Output is correct
29 Correct 903 ms 45392 KB Output is correct
30 Correct 1438 ms 35232 KB Output is correct
31 Correct 1292 ms 28560 KB Output is correct
32 Correct 248 ms 10324 KB Output is correct
33 Correct 315 ms 10664 KB Output is correct
34 Correct 175 ms 39128 KB Output is correct
35 Correct 600 ms 26932 KB Output is correct
36 Correct 1082 ms 43164 KB Output is correct
37 Correct 868 ms 43344 KB Output is correct
38 Correct 845 ms 42968 KB Output is correct
39 Correct 737 ms 35620 KB Output is correct
40 Correct 0 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 424 KB Output is correct
7 Correct 0 ms 504 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 420 KB Output is correct
12 Correct 358 ms 12792 KB Output is correct
13 Correct 207 ms 12628 KB Output is correct
14 Correct 303 ms 10136 KB Output is correct
15 Correct 323 ms 9828 KB Output is correct
16 Correct 210 ms 8088 KB Output is correct
17 Correct 302 ms 9812 KB Output is correct
18 Correct 288 ms 9552 KB Output is correct
19 Correct 517 ms 15696 KB Output is correct
20 Correct 962 ms 8772 KB Output is correct
21 Correct 153 ms 5496 KB Output is correct
22 Correct 969 ms 10432 KB Output is correct
23 Correct 120 ms 14164 KB Output is correct
24 Correct 530 ms 11092 KB Output is correct
25 Correct 783 ms 15560 KB Output is correct
26 Correct 651 ms 15588 KB Output is correct
27 Correct 599 ms 14956 KB Output is correct
28 Correct 278 ms 43092 KB Output is correct
29 Correct 794 ms 45428 KB Output is correct
30 Correct 1364 ms 35120 KB Output is correct
31 Correct 1267 ms 28752 KB Output is correct
32 Correct 235 ms 10116 KB Output is correct
33 Correct 301 ms 10800 KB Output is correct
34 Correct 206 ms 39252 KB Output is correct
35 Correct 574 ms 26832 KB Output is correct
36 Correct 1126 ms 43340 KB Output is correct
37 Correct 887 ms 43420 KB Output is correct
38 Correct 898 ms 42824 KB Output is correct
39 Correct 361 ms 81112 KB Output is correct
40 Correct 1369 ms 81988 KB Output is correct
41 Correct 1881 ms 67268 KB Output is correct
42 Correct 1703 ms 52564 KB Output is correct
43 Correct 313 ms 76880 KB Output is correct
44 Correct 270 ms 10576 KB Output is correct
45 Correct 765 ms 35732 KB Output is correct
46 Correct 1437 ms 80812 KB Output is correct
47 Correct 1510 ms 80780 KB Output is correct
48 Correct 1388 ms 80556 KB Output is correct
49 Correct 0 ms 856 KB Output is correct