답안 #5241 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5241	2014-02-21T15:28:14 Z	ainta	게임 (IOI13_game)	C++	100 / 100	9400 ms	105488 KB

game

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

int rr, cc;
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;
}

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

struct Seg_X{
	Seg_X *c1, *c2;
	Seg_Y *cy;
	long long G;
};
Seg_X *root;

void init(int R, int C) {
	root = new Seg_X();
	rr = R, cc = C;
}

void UDT_Y(Seg_Y *node, int b, int e, int y, long long K){
	int m = (b + e) >> 1;
	if (node->K){
		if (node->K == y){
			node->G = K;
			return;
		}
		if (node->K <= m)node->c1 = new Seg_Y(node->K), node->c1->G = node->G;
		else node->c2 = new Seg_Y(node->K), node->c2->G = node->G;
		node->K = 0;
	}
	if (y <= m){
		if (!node->c1) node->c1 = new Seg_Y(y);
		UDT_Y(node->c1, b, m, y, K);
	}
	else {
		if (!node->c2) node->c2 = new Seg_Y(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(Seg_Y *node, int b, int e, int y){
	if (node == NULL)return 0;
	if (node->K){
		if (node->K == y)return node->G;
		return 0;
	}
	int m = (b + e) >> 1;
	if (y <= m)return Gap(node->c1, b, m, y);
	else return Gap(node->c2, m + 1, e, y);
}

void UDT_X(Seg_X *node, int b, int e, int x, int y, long long K){
	if (!node->cy)node->cy = new Seg_Y(y);
	if (b == e){
		UDT_Y(node->cy, 1, cc, y, K);
		return;
	}
	int m = (b + e) >> 1;
	long long r = 0;
	if (!node->c1)node->c1 = new Seg_X();
	if (!node->c2)node->c2 = new Seg_X();
	if (x <= m)UDT_X(node->c1, b, m, x, y, K);
	else UDT_X(node->c2, m + 1, e, x, y, K);
	r = Gap(node->c2->cy, 1, cc, y);
	r = gcd2(Gap(node->c1->cy, 1, cc, y), r);
	UDT_Y(node->cy, 1, cc, y, r);
}

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

long long Calc2(Seg_Y *node, int b, int e, int Q, int V){
	if (!node)return 0;
	if (node->K){
		if (node->K >= Q && node->K <= V)return node->G;
		return 0;
	}
	if (b == Q && e == V)return node->G;
	int m = (b + e) >> 1;
	long long r = 0;
	if (Q <= m && node->c1)r = Calc2(node->c1, b, m, Q, min(V,m));
	if (V > m && node->c2)r = gcd2(Calc2(node->c2, m + 1, e, max(m + 1, Q), V), r);
	return r;
}
long long Calc(Seg_X *node, int b, int e, int P, int Q, int U, int V){
	if (b == P && e == U)return Calc2(node->cy, 1, cc, Q, V);
	int m = (b + e) >> 1;
	long long r = 0;
	if (P <= m && node->c1) r = Calc(node->c1, b, m, P, Q, min(U, m), V);
	if (U > m && node->c2) r = gcd2(Calc(node->c2, m + 1, e, max(P, m + 1), Q, U, V), r);
	return r;
}

long long calculate(int P, int Q, int U, int V) {
	return  Calc(root, 1, rr, 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	824 ms	5828 KB	Output is correct
5	Correct	580 ms	5828 KB	Output is correct
6	Correct	760 ms	5960 KB	Output is correct
7	Correct	840 ms	5960 KB	Output is correct
8	Correct	496 ms	3452 KB	Output is correct
9	Correct	844 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	1384 ms	9260 KB	Output is correct
13	Correct	3160 ms	5960 KB	Output is correct
14	Correct	412 ms	1340 KB	Output is correct
15	Correct	3684 ms	7676 KB	Output is correct
16	Correct	296 ms	11372 KB	Output is correct
17	Correct	1248 ms	6488 KB	Output is correct
18	Correct	2316 ms	11504 KB	Output is correct
19	Correct	1944 ms	11372 KB	Output is correct
20	Correct	1716 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	792 ms	5828 KB	Output is correct
13	Correct	536 ms	5828 KB	Output is correct
14	Correct	700 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	776 ms	5960 KB	Output is correct
18	Correct	676 ms	5960 KB	Output is correct
19	Correct	1328 ms	9260 KB	Output is correct
20	Correct	3100 ms	5960 KB	Output is correct
21	Correct	380 ms	1340 KB	Output is correct
22	Correct	3652 ms	7676 KB	Output is correct
23	Correct	268 ms	11372 KB	Output is correct
24	Correct	1264 ms	6488 KB	Output is correct
25	Correct	2220 ms	11504 KB	Output is correct
26	Correct	1800 ms	11372 KB	Output is correct
27	Correct	1680 ms	11372 KB	Output is correct
28	Correct	844 ms	48068 KB	Output is correct
29	Correct	2152 ms	40544 KB	Output is correct
30	Correct	7216 ms	42392 KB	Output is correct
31	Correct	6456 ms	32096 KB	Output is correct
32	Correct	820 ms	1736 KB	Output is correct
33	Correct	1088 ms	5432 KB	Output is correct
34	Correct	384 ms	40544 KB	Output is correct
35	Correct	1572 ms	20744 KB	Output is correct
36	Correct	2868 ms	40544 KB	Output is correct
37	Correct	2316 ms	40676 KB	Output is correct
38	Correct	2256 ms	40676 KB	Output is correct
39	Correct	1960 ms	31304 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	768 ms	5828 KB	Output is correct
13	Correct	536 ms	5828 KB	Output is correct
14	Correct	704 ms	5960 KB	Output is correct
15	Correct	796 ms	5960 KB	Output is correct
16	Correct	488 ms	3452 KB	Output is correct
17	Correct	768 ms	5960 KB	Output is correct
18	Correct	704 ms	5960 KB	Output is correct
19	Correct	1320 ms	9260 KB	Output is correct
20	Correct	2984 ms	5960 KB	Output is correct
21	Correct	400 ms	1340 KB	Output is correct
22	Correct	3664 ms	7676 KB	Output is correct
23	Correct	292 ms	11372 KB	Output is correct
24	Correct	1256 ms	6488 KB	Output is correct
25	Correct	2176 ms	11504 KB	Output is correct
26	Correct	1836 ms	11372 KB	Output is correct
27	Correct	1656 ms	11372 KB	Output is correct
28	Correct	772 ms	48068 KB	Output is correct
29	Correct	2068 ms	40544 KB	Output is correct
30	Correct	7176 ms	42392 KB	Output is correct
31	Correct	6420 ms	32096 KB	Output is correct
32	Correct	824 ms	1736 KB	Output is correct
33	Correct	1108 ms	5432 KB	Output is correct
34	Correct	396 ms	40544 KB	Output is correct
35	Correct	1544 ms	20744 KB	Output is correct
36	Correct	2812 ms	40544 KB	Output is correct
37	Correct	2308 ms	40676 KB	Output is correct
38	Correct	2208 ms	40676 KB	Output is correct
39	Correct	1048 ms	105488 KB	Output is correct
40	Correct	3192 ms	87140 KB	Output is correct
41	Correct	9400 ms	90176 KB	Output is correct
42	Correct	8744 ms	68000 KB	Output is correct
43	Correct	732 ms	87272 KB	Output is correct
44	Correct	1124 ms	1736 KB	Output is correct
45	Correct	1992 ms	31304 KB	Output is correct
46	Correct	3740 ms	87272 KB	Output is correct
47	Correct	3712 ms	87272 KB	Output is correct
48	Correct	3484 ms	87272 KB	Output is correct
49	Correct	0 ms	1208 KB	Output is correct

답안 #5241

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