oj.uz

Submission #545973

# Submission time Handle Problem Language Result Execution time Memory
545973 2022-04-05T18:53:56 Z sliviu Game (IOI13_game) C++17
100 / 100
 2904 ms 82160 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 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 0 ms 288 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 288 KB Output is correct
12 Correct 1 ms 284 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 454 ms 12796 KB Output is correct
5 Correct 343 ms 12476 KB Output is correct
6 Correct 384 ms 9984 KB Output is correct
7 Correct 478 ms 9800 KB Output is correct
8 Correct 306 ms 8076 KB Output is correct
9 Correct 399 ms 9780 KB Output is correct
10 Correct 412 ms 9548 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 288 KB Output is correct
12 Correct 748 ms 15568 KB Output is correct
13 Correct 1424 ms 8824 KB Output is correct
14 Correct 224 ms 5500 KB Output is correct
15 Correct 1544 ms 10580 KB Output is correct
16 Correct 216 ms 13988 KB Output is correct
17 Correct 604 ms 11048 KB Output is correct
18 Correct 1166 ms 15512 KB Output is correct
19 Correct 969 ms 15580 KB Output is correct
20 Correct 894 ms 15028 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 284 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 468 ms 12664 KB Output is correct
13 Correct 321 ms 12536 KB Output is correct
14 Correct 391 ms 10048 KB Output is correct
15 Correct 465 ms 9788 KB Output is correct
16 Correct 289 ms 8084 KB Output is correct
17 Correct 465 ms 9880 KB Output is correct
18 Correct 402 ms 9604 KB Output is correct
19 Correct 764 ms 15488 KB Output is correct
20 Correct 1334 ms 8908 KB Output is correct
21 Correct 216 ms 5552 KB Output is correct
22 Correct 1486 ms 10476 KB Output is correct
23 Correct 170 ms 14032 KB Output is correct
24 Correct 585 ms 11052 KB Output is correct
25 Correct 1212 ms 15532 KB Output is correct
26 Correct 944 ms 15696 KB Output is correct
27 Correct 906 ms 15092 KB Output is correct
28 Correct 405 ms 43192 KB Output is correct
29 Correct 1180 ms 45308 KB Output is correct
30 Correct 2154 ms 35152 KB Output is correct
31 Correct 1988 ms 28560 KB Output is correct
32 Correct 362 ms 10184 KB Output is correct
33 Correct 421 ms 10720 KB Output is correct
34 Correct 245 ms 39204 KB Output is correct
35 Correct 860 ms 26936 KB Output is correct
36 Correct 1584 ms 43384 KB Output is correct
37 Correct 1222 ms 43576 KB Output is correct
38 Correct 1289 ms 42836 KB Output is correct
39 Correct 1080 ms 35816 KB Output is correct
40 Correct 0 ms 340 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 454 ms 12712 KB Output is correct
13 Correct 321 ms 12512 KB Output is correct
14 Correct 399 ms 10060 KB Output is correct
15 Correct 467 ms 9764 KB Output is correct
16 Correct 275 ms 8028 KB Output is correct
17 Correct 403 ms 9876 KB Output is correct
18 Correct 372 ms 9420 KB Output is correct
19 Correct 709 ms 15672 KB Output is correct
20 Correct 1291 ms 8736 KB Output is correct
21 Correct 226 ms 5608 KB Output is correct
22 Correct 1411 ms 10616 KB Output is correct
23 Correct 177 ms 14024 KB Output is correct
24 Correct 553 ms 10952 KB Output is correct
25 Correct 999 ms 15588 KB Output is correct
26 Correct 841 ms 15668 KB Output is correct
27 Correct 766 ms 15180 KB Output is correct
28 Correct 371 ms 43224 KB Output is correct
29 Correct 1048 ms 45456 KB Output is correct
30 Correct 2031 ms 35220 KB Output is correct
31 Correct 1829 ms 28576 KB Output is correct
32 Correct 318 ms 10184 KB Output is correct
33 Correct 463 ms 10648 KB Output is correct
34 Correct 228 ms 39048 KB Output is correct
35 Correct 739 ms 26892 KB Output is correct
36 Correct 1635 ms 43340 KB Output is correct
37 Correct 1241 ms 43548 KB Output is correct
38 Correct 1197 ms 42812 KB Output is correct
39 Correct 512 ms 81152 KB Output is correct
40 Correct 1806 ms 82160 KB Output is correct
41 Correct 2904 ms 67076 KB Output is correct
42 Correct 2506 ms 52344 KB Output is correct
43 Correct 443 ms 76724 KB Output is correct
44 Correct 377 ms 10704 KB Output is correct
45 Correct 971 ms 35608 KB Output is correct
46 Correct 2188 ms 80996 KB Output is correct
47 Correct 2191 ms 80872 KB Output is correct
48 Correct 2102 ms 80424 KB Output is correct
49 Correct 0 ms 212 KB Output is correct