답안 #4653 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4653	2013-11-15T19:27:39 Z	ainta	게임 (IOI13_game)	C++	100 / 100	10360 ms	84764 KB

game

#include "game.h"
#include <stdio.h>
#include <algorithm>
using namespace std;

int N, M;

struct Y_Seg{
	Y_Seg *c1, *c2;
	int b;
	long long G;
	Y_Seg(int p){ c1 = c2 = NULL, G = 0, b = p; }
};

struct X_Seg{
	X_Seg *c1, *c2;
	Y_Seg *cy;
	X_Seg(){ c1 = c2 = NULL, cy = NULL; }
};

X_Seg *root;

long long gcd2(long long X, long long Y) {
	long long tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}

void init(int R, int C) {
	N = R, M = C;
	root = new X_Seg();
}

void UDT_Y(Y_Seg *node, int b, int e, int y, long long K){
	int t, m = (b + e) >> 1;
	if (node->b){
		if (node->b == y){
			node->G = K;
			return;
		}
		else{
			t = node->b;
			node->b = 0;
			if (t <= m){
				node->c1 = new Y_Seg(t);
				node->c1->G = node->G;
			}
			else{
				node->c2 = new Y_Seg(t);
				node->c2->G = node->G;
			}
		}
	}
	if (y <= m){
		if (!node->c1)node->c1 = new Y_Seg(y);
		UDT_Y(node->c1, b, m, y, K);
	}
	else{
		if (!node->c2)node->c2 = new Y_Seg(y);
		UDT_Y(node->c2, m + 1, e, y, K);
	}
	node->G = gcd2(node->c1 ? node->c1->G : 0, node->c2 ? node->c2->G : 0);
}

long long Gap_Leaf(X_Seg *node, int y){
	if (node == NULL)return 0;
	Y_Seg *p = node->cy;
	int b = 1, e = M, m;
	while (p != NULL){
		if (p->b){
			return p->b == y ? p->G : 0;
		}
		m = (b + e) >> 1;
		if (m >= y) p = p->c1, e = m;
		else p = p->c2, b = m + 1;
	}
	return 0;
}

void UDT_X(X_Seg *node, int b, int e, int x, int y, long long K){
	if (!node->cy)node->cy = new Y_Seg(y);
	if (b == e){
		UDT_Y(node->cy, 1, M, y, K);
		return;
	}
	int m = (b + e) >> 1;
	long long G = 0;
	if (x <= m){
		if (!node->c1)node->c1 = new X_Seg();
		UDT_X(node->c1, b, m, x, y, K);
	}
	else{
		if (!node->c2)node->c2 = new X_Seg();
		UDT_X(node->c2, m + 1, e, x, y, K);
	}
	G = gcd2(Gap_Leaf(node->c1, y), Gap_Leaf(node->c2, y));
	UDT_Y(node->cy, 1, M, y, G);
}

void update(int P, int Q, long long K) {
	UDT_X(root, 1, N, P+1, Q+1, K);
}

long long CalcY(Y_Seg *node, int b, int e, int s, int l){
	if (!node)return 0;
	if (node->b){
		if (s <= node->b && node->b <= l) return node->G;
		return 0;
	}
	if (b == s && e == l)return node->G;
	int m = (b + e) >> 1;
	long long G = 0;
	if (m >= s && node->c1)G = CalcY(node->c1, b, m, s, min(l, m));
	if (m < l && node->c2)G = gcd2(G, CalcY(node->c2, m + 1, e, max(s, m + 1), l));
	return G;
}

long long CalcX(X_Seg *node, int b, int e, int P, int Q, int U, int V){
	int m = (b + e) >> 1;
	if (b == P && e == U){
		return CalcY(node->cy, 1, M, Q, V);
	}
	long long G = 0;
	if (m >= P){
		if (node->c1)G = CalcX(node->c1, b, m, P, Q, min(m, U), V);
	}
	if (m < U){
		if (node->c2)G = gcd2(G, CalcX(node->c2, m + 1, e, max(P, m + 1), Q, U, V));
	}
	return G;
}

long long calculate(int P, int Q, int U, int V) {
	return CalcX(root, 1, N, P+1, Q+1, U+1, V+1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1208 KB	Output is correct
2	Correct	0 ms	1208 KB	Output is correct
3	Correct	0 ms	1208 KB	Output is correct
4	Correct	788 ms	5828 KB	Output is correct
5	Correct	532 ms	5828 KB	Output is correct
6	Correct	708 ms	5960 KB	Output is correct
7	Correct	808 ms	5960 KB	Output is correct
8	Correct	500 ms	3452 KB	Output is correct
9	Correct	772 ms	5960 KB	Output is correct
10	Correct	692 ms	5960 KB	Output is correct
11	Correct	0 ms	1208 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1208 KB	Output is correct
2	Correct	0 ms	1208 KB	Output is correct
3	Correct	0 ms	1208 KB	Output is correct
4	Correct	0 ms	1208 KB	Output is correct
5	Correct	0 ms	1208 KB	Output is correct
6	Correct	0 ms	1208 KB	Output is correct
7	Correct	0 ms	1208 KB	Output is correct
8	Correct	0 ms	1208 KB	Output is correct
9	Correct	0 ms	1208 KB	Output is correct
10	Correct	0 ms	1208 KB	Output is correct
11	Correct	0 ms	1208 KB	Output is correct
12	Correct	1288 ms	9260 KB	Output is correct
13	Correct	3068 ms	5960 KB	Output is correct
14	Correct	400 ms	1340 KB	Output is correct
15	Correct	3588 ms	7544 KB	Output is correct
16	Correct	268 ms	11372 KB	Output is correct
17	Correct	1188 ms	6488 KB	Output is correct
18	Correct	2076 ms	11372 KB	Output is correct
19	Correct	1680 ms	11372 KB	Output is correct
20	Correct	1604 ms	11372 KB	Output is correct
21	Correct	0 ms	1208 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1208 KB	Output is correct
2	Correct	0 ms	1208 KB	Output is correct
3	Correct	0 ms	1208 KB	Output is correct
4	Correct	0 ms	1208 KB	Output is correct
5	Correct	0 ms	1208 KB	Output is correct
6	Correct	0 ms	1208 KB	Output is correct
7	Correct	0 ms	1208 KB	Output is correct
8	Correct	0 ms	1208 KB	Output is correct
9	Correct	0 ms	1208 KB	Output is correct
10	Correct	0 ms	1208 KB	Output is correct
11	Correct	0 ms	1208 KB	Output is correct
12	Correct	780 ms	5828 KB	Output is correct
13	Correct	516 ms	5828 KB	Output is correct
14	Correct	700 ms	5960 KB	Output is correct
15	Correct	780 ms	5960 KB	Output is correct
16	Correct	500 ms	3452 KB	Output is correct
17	Correct	752 ms	5960 KB	Output is correct
18	Correct	672 ms	5960 KB	Output is correct
19	Correct	1264 ms	9260 KB	Output is correct
20	Correct	3088 ms	5960 KB	Output is correct
21	Correct	412 ms	1340 KB	Output is correct
22	Correct	3584 ms	7544 KB	Output is correct
23	Correct	280 ms	11372 KB	Output is correct
24	Correct	1176 ms	6488 KB	Output is correct
25	Correct	2032 ms	11372 KB	Output is correct
26	Correct	1712 ms	11372 KB	Output is correct
27	Correct	1604 ms	11372 KB	Output is correct
28	Correct	728 ms	37904 KB	Output is correct
29	Correct	1952 ms	30380 KB	Output is correct
30	Correct	7980 ms	36716 KB	Output is correct
31	Correct	7384 ms	27740 KB	Output is correct
32	Correct	872 ms	1736 KB	Output is correct
33	Correct	1112 ms	5300 KB	Output is correct
34	Correct	372 ms	30380 KB	Output is correct
35	Correct	1476 ms	15332 KB	Output is correct
36	Correct	2640 ms	30380 KB	Output is correct
37	Correct	2208 ms	30512 KB	Output is correct
38	Correct	2104 ms	30512 KB	Output is correct
39	Correct	1852 ms	23384 KB	Output is correct
40	Correct	0 ms	1208 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1208 KB	Output is correct
2	Correct	0 ms	1208 KB	Output is correct
3	Correct	0 ms	1208 KB	Output is correct
4	Correct	0 ms	1208 KB	Output is correct
5	Correct	0 ms	1208 KB	Output is correct
6	Correct	0 ms	1208 KB	Output is correct
7	Correct	0 ms	1208 KB	Output is correct
8	Correct	0 ms	1208 KB	Output is correct
9	Correct	0 ms	1208 KB	Output is correct
10	Correct	0 ms	1208 KB	Output is correct
11	Correct	0 ms	1208 KB	Output is correct
12	Correct	804 ms	5828 KB	Output is correct
13	Correct	520 ms	5828 KB	Output is correct
14	Correct	704 ms	5960 KB	Output is correct
15	Correct	804 ms	5960 KB	Output is correct
16	Correct	492 ms	3452 KB	Output is correct
17	Correct	784 ms	5960 KB	Output is correct
18	Correct	668 ms	5960 KB	Output is correct
19	Correct	1268 ms	9260 KB	Output is correct
20	Correct	3060 ms	5960 KB	Output is correct
21	Correct	388 ms	1340 KB	Output is correct
22	Correct	3560 ms	7544 KB	Output is correct
23	Correct	272 ms	11372 KB	Output is correct
24	Correct	1164 ms	6488 KB	Output is correct
25	Correct	2020 ms	11372 KB	Output is correct
26	Correct	1716 ms	11372 KB	Output is correct
27	Correct	1552 ms	11372 KB	Output is correct
28	Correct	700 ms	37904 KB	Output is correct
29	Correct	1996 ms	30380 KB	Output is correct
30	Correct	7984 ms	36716 KB	Output is correct
31	Correct	7684 ms	27740 KB	Output is correct
32	Correct	856 ms	1736 KB	Output is correct
33	Correct	1104 ms	5300 KB	Output is correct
34	Correct	368 ms	30380 KB	Output is correct
35	Correct	1492 ms	15332 KB	Output is correct
36	Correct	2656 ms	30380 KB	Output is correct
37	Correct	2148 ms	30512 KB	Output is correct
38	Correct	2068 ms	30512 KB	Output is correct
39	Correct	964 ms	84764 KB	Output is correct
40	Correct	3076 ms	66416 KB	Output is correct
41	Correct	10360 ms	78692 KB	Output is correct
42	Correct	9776 ms	59288 KB	Output is correct
43	Correct	672 ms	66416 KB	Output is correct
44	Correct	1172 ms	1736 KB	Output is correct
45	Correct	1880 ms	23384 KB	Output is correct
46	Correct	3444 ms	66416 KB	Output is correct
47	Correct	3384 ms	66548 KB	Output is correct
48	Correct	3276 ms	66416 KB	Output is correct
49	Correct	0 ms	1208 KB	Output is correct

답안 #4653

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