답안 #1090844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1090844	2024-09-18T22:22:10 Z	LeonidCuk	게임 (IOI13_game)	C++17	100 / 100	1881 ms	81988 KB

game

#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

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	356 KB	Output is correct
7	Correct	356 KB	Output is correct
8	Correct	356 KB	Output is correct
9	Correct	356 KB	Output is correct
10	Correct	356 KB	Output is correct
11	Correct	356 KB	Output is correct
12	Correct	356 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #1090844

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.0 / 17.0

Subtask #5 20.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
17.0 / 17.0

Subtask #5
20.0 / 20.0