답안 #426153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
426153	2021-06-13T14:44:11 Z	frodakcin	게임 (IOI13_game)	C++17	80 / 100	5104 ms	256000 KB

game

#include "game.h"
#include <cstdio>

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

using ll = long long;

const int MU = 2.2e4+10;
const int MQ = 2.5e5+10;

const int M1 = 30 * 30 * MU / 2;
const int M2 = 30 * MU;

int R, C, X1, X2;
ll st1[M1]; int l1[M1], r1[M1];
int st2[M2], l2[M2], r2[M2], root;

void init(int R, int C) {
	::R=R, ::C=C;
}

void upd1(int& n, int l, int r, int Q, ll K)
{
	if(!n) n=++X1;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(Q<m) upd1(l1[n], l, m, Q, K);
		else upd1(r1[n], m, r, Q, K);
		st1[n]=gcd(st1[l1[n]], st1[r1[n]]);
	}
	else
		st1[n]=K;
}

void up(int& p, int a, int b, int l, int r, int Q)
{
	if(!p) p=++X1;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(Q<m) up(l1[p], l1[a], l1[b], l, m, Q);
		else up(r1[p], r1[a], r1[b], m, r, Q);
	}
	st1[p]=gcd(st1[a], st1[b]);
}

void upd2(int& n, int l, int r, int P, int Q, ll K)
{
	if(!n) n=++X2;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(P<m) upd2(l2[n], l, m, P, Q, K);
		else upd2(r2[n], m, r, P, Q, K);
		up(st2[n], st2[l2[n]], st2[r2[n]], 0, C, Q);
	}
	else
		upd1(st2[n], 0, C, Q, K);
}

void update(int P, int Q, long long K) {
	upd2(root, 0, R, P, Q, K);
}

ll qry1(int n, int l, int r, int Q, int V)
{
	if(!n) return 0;
	if(Q <= l && r <= V) return st1[n];
	else
	{
		int m=l+(r-l)/2;
		ll v=0;
		if(Q<m) v = gcd(v, qry1(l1[n], l, m, Q, V));
		if(m<V) v = gcd(v, qry1(r1[n], m, r, Q, V));
		return v;
	}
}

ll qry2(int n, int l, int r, int P, int U, int Q, int V)
{
	if(!n) return 0;
	if(P <= l && r <= U) return qry1(st2[n], 0, C, Q, V);
	else
	{
		int m=l+(r-l)/2;
		ll v=0;
		if(P<m) v = gcd(v, qry2(l2[n], l, m, P, U, Q, V));
		if(m<U) v = gcd(v, qry2(r2[n], m, r, P, U, Q, V));
		return v;
	}
}

long long calculate(int P, int Q, int U, int V) {
	return qry2(root, 0, R, P, U+1, Q, V+1);
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	604 ms	11864 KB	Output is correct
5	Correct	472 ms	12084 KB	Output is correct
6	Correct	478 ms	8816 KB	Output is correct
7	Correct	585 ms	8552 KB	Output is correct
8	Correct	348 ms	7620 KB	Output is correct
9	Correct	492 ms	8720 KB	Output is correct
10	Correct	457 ms	8292 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	284 KB	Output is correct
5	Correct	1 ms	280 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	951 ms	13352 KB	Output is correct
13	Correct	1510 ms	6840 KB	Output is correct
14	Correct	292 ms	4144 KB	Output is correct
15	Correct	1870 ms	8212 KB	Output is correct
16	Correct	206 ms	12832 KB	Output is correct
17	Correct	742 ms	9780 KB	Output is correct
18	Correct	1442 ms	13016 KB	Output is correct
19	Correct	1063 ms	15448 KB	Output is correct
20	Correct	1034 ms	14856 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	280 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	284 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	567 ms	11604 KB	Output is correct
13	Correct	427 ms	11844 KB	Output is correct
14	Correct	452 ms	8796 KB	Output is correct
15	Correct	585 ms	8368 KB	Output is correct
16	Correct	358 ms	7420 KB	Output is correct
17	Correct	524 ms	8600 KB	Output is correct
18	Correct	445 ms	8196 KB	Output is correct
19	Correct	899 ms	13252 KB	Output is correct
20	Correct	1507 ms	6732 KB	Output is correct
21	Correct	292 ms	4064 KB	Output is correct
22	Correct	1799 ms	7928 KB	Output is correct
23	Correct	198 ms	12756 KB	Output is correct
24	Correct	874 ms	9672 KB	Output is correct
25	Correct	1403 ms	13068 KB	Output is correct
26	Correct	1123 ms	15504 KB	Output is correct
27	Correct	1012 ms	14852 KB	Output is correct
28	Correct	750 ms	136080 KB	Output is correct
29	Correct	2044 ms	150888 KB	Output is correct
30	Correct	5104 ms	108764 KB	Output is correct
31	Correct	4885 ms	84796 KB	Output is correct
32	Correct	605 ms	10312 KB	Output is correct
33	Correct	732 ms	11428 KB	Output is correct
34	Correct	504 ms	144536 KB	Output is correct
35	Correct	1616 ms	80052 KB	Output is correct
36	Correct	3952 ms	148568 KB	Output is correct
37	Correct	2795 ms	148772 KB	Output is correct
38	Correct	2569 ms	148320 KB	Output is correct
39	Correct	2126 ms	116532 KB	Output is correct
40	Correct	1 ms	204 KB	Output is correct

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	284 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	284 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	549 ms	11660 KB	Output is correct
13	Correct	429 ms	11944 KB	Output is correct
14	Correct	468 ms	8832 KB	Output is correct
15	Correct	523 ms	8492 KB	Output is correct
16	Correct	346 ms	7476 KB	Output is correct
17	Correct	545 ms	8400 KB	Output is correct
18	Correct	459 ms	8016 KB	Output is correct
19	Correct	905 ms	13172 KB	Output is correct
20	Correct	1492 ms	6588 KB	Output is correct
21	Correct	294 ms	3828 KB	Output is correct
22	Correct	1834 ms	7872 KB	Output is correct
23	Correct	200 ms	12552 KB	Output is correct
24	Correct	771 ms	9480 KB	Output is correct
25	Correct	1301 ms	12944 KB	Output is correct
26	Correct	1034 ms	15572 KB	Output is correct
27	Correct	943 ms	14804 KB	Output is correct
28	Correct	752 ms	136160 KB	Output is correct
29	Correct	1939 ms	150888 KB	Output is correct
30	Correct	5039 ms	108792 KB	Output is correct
31	Correct	4798 ms	84876 KB	Output is correct
32	Correct	552 ms	10216 KB	Output is correct
33	Correct	702 ms	11468 KB	Output is correct
34	Correct	487 ms	144548 KB	Output is correct
35	Correct	1892 ms	80248 KB	Output is correct
36	Correct	3940 ms	148580 KB	Output is correct
37	Correct	2716 ms	148760 KB	Output is correct
38	Correct	2587 ms	148368 KB	Output is correct
39	Runtime error	814 ms	256000 KB	Execution killed with signal 11
40	Halted	0 ms	0 KB	-