Submission #4624

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4624	2013-11-13T02:50:55 Z	cki86201	Game (IOI13_game)	C++	100 / 100	8452 ms	76316 KB

game

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

typedef long long ll;

int R,C;

ll gc(ll x,ll y){
	ll tmp=-1;
	while(x!=tmp&&y)tmp=x,x=y,y=tmp%y;
	return x;
}

struct node1{
	node1(){}
	node1(int s,int d,ll x):s(s),d(d),x(x),right(0),left(0){}
	int s,d;
	ll x;
	node1 *right,*left;
};

struct node2{
	node1 *x;
	node2 *right,*left;
}*tree;

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

void update1(node1 *R,int u,ll K)
{
	int s = R->s,d = R->d;
	if(s == d){R->x = K;return;}
	int m = (s+d)>>1;
	node1 **t = &(u<=m?R->left:R->right);
	if(*t==NULL)*t = new node1(u,u,K);
	else if((*t)->s<=u && u<=(*t)->d)update1(*t,u,K);
	else{
		while((u>m) ^ ((*t)->s<=m)){
			if(u<=m)d=m;
			else s=m+1;
			m=(s+d)>>1;
		}
		node1 *n = new node1(s,d,0);
		if((*t)->s<=m)n->left = *t;
		else n->right = *t;
		*t = n;
		update1(n,u,K);
	}
	R->x = gc(R->left?R->left->x:0,R->right?R->right->x:0);
}

ll read1(node1 *R,int l,int r)
{
	if(!R)return 0;
	int s = R->s, d = R->d;
	if(d<l||r<s)return 0;
	if(l<=s&&d<=r)return R->x;
	return gc(R->left?read1(R->left,l,r):0,R->right?read1(R->right,l,r):0);
}

void update2(node2 *R,int u1,int u2,int s,int d,ll K)
{
	if(s==d){
		if(!R->x)R->x = new node1(1,C,0);
		update1(R->x,u2,K);
		return;
	}
	int m = (s+d)>>1;
	if(u1<=m){
		if(!R->left)R->left = new node2();
		update2(R->left,u1,u2,s,m,K);
	}
	else{
		if(!R->right)R->right =new node2();
		update2(R->right,u1,u2,m+1,d,K);
	}
	ll L = gc((R->left)?read1(R->left->x,u2,u2):0,(R->right)?read1(R->right->x,u2,u2):0);
	if(!R->x)R->x = new node1(1,C,0);
	update1(R->x,u2,L);
}

ll read2(node2 *R,int l1,int r1,int l2,int r2,int s,int d)
{
	int m = (s+d)>>1;
	if(l1<=s&&d<=r1)return read1(R->x,l2,r2);
	if(r1<s||d<l1)return 0;
	return gc((R->left)?read2(R->left,l1,r1,l2,r2,s,m):0,(R->right)?read2(R->right,l1,r1,l2,r2,m+1,d):0);
}

void update(int P, int Q, ll K){
	++P,++Q;
	update2(tree,P,Q,1,R,K);
}

ll calculate(int P, int Q, int U, int V){
	++P,++Q,++U,++V;
	return read2(tree,P,U,Q,V,1,R);
}

Subtask #1
10.0 / 10.0

#	Verdict	Memory	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

#	Verdict	Execution time	Memory	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	928 ms	5168 KB	Output is correct
5	Correct	652 ms	5168 KB	Output is correct
6	Correct	740 ms	5168 KB	Output is correct
7	Correct	864 ms	5168 KB	Output is correct
8	Correct	536 ms	3056 KB	Output is correct
9	Correct	852 ms	5168 KB	Output is correct
10	Correct	808 ms	5168 KB	Output is correct
11	Correct	0 ms	1208 KB	Output is correct

Subtask #3
26.0 / 26.0

#	Verdict	Execution time	Memory	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	1760 ms	8336 KB	Output is correct
13	Correct	3396 ms	5036 KB	Output is correct
14	Correct	372 ms	1208 KB	Output is correct
15	Correct	3832 ms	6356 KB	Output is correct
16	Correct	304 ms	10052 KB	Output is correct
17	Correct	1248 ms	5828 KB	Output is correct
18	Correct	2212 ms	10052 KB	Output is correct
19	Correct	1884 ms	10052 KB	Output is correct
20	Correct	1764 ms	10052 KB	Output is correct
21	Correct	0 ms	1208 KB	Output is correct

Subtask #4
17.0 / 17.0

#	Verdict	Execution time	Memory	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	928 ms	5168 KB	Output is correct
13	Correct	660 ms	5168 KB	Output is correct
14	Correct	740 ms	5168 KB	Output is correct
15	Correct	864 ms	5168 KB	Output is correct
16	Correct	532 ms	3056 KB	Output is correct
17	Correct	856 ms	5168 KB	Output is correct
18	Correct	756 ms	5168 KB	Output is correct
19	Correct	1776 ms	8336 KB	Output is correct
20	Correct	3372 ms	5036 KB	Output is correct
21	Correct	368 ms	1208 KB	Output is correct
22	Correct	3828 ms	6356 KB	Output is correct
23	Correct	308 ms	10052 KB	Output is correct
24	Correct	1244 ms	5828 KB	Output is correct
25	Correct	2204 ms	10052 KB	Output is correct
26	Correct	1864 ms	10052 KB	Output is correct
27	Correct	1728 ms	10052 KB	Output is correct
28	Correct	716 ms	35660 KB	Output is correct
29	Correct	2660 ms	35264 KB	Output is correct
30	Correct	6232 ms	29984 KB	Output is correct
31	Correct	5476 ms	22856 KB	Output is correct
32	Correct	580 ms	1340 KB	Output is correct
33	Correct	776 ms	2000 KB	Output is correct
34	Correct	408 ms	35264 KB	Output is correct
35	Correct	1616 ms	18104 KB	Output is correct
36	Correct	3020 ms	35264 KB	Output is correct
37	Correct	2424 ms	35264 KB	Output is correct
38	Correct	2396 ms	35264 KB	Output is correct
39	Correct	2036 ms	27212 KB	Output is correct
40	Correct	0 ms	1208 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	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	924 ms	5168 KB	Output is correct
13	Correct	640 ms	5168 KB	Output is correct
14	Correct	752 ms	5168 KB	Output is correct
15	Correct	868 ms	5168 KB	Output is correct
16	Correct	528 ms	3056 KB	Output is correct
17	Correct	812 ms	5168 KB	Output is correct
18	Correct	768 ms	5168 KB	Output is correct
19	Correct	1704 ms	8336 KB	Output is correct
20	Correct	3324 ms	5036 KB	Output is correct
21	Correct	364 ms	1208 KB	Output is correct
22	Correct	3816 ms	6356 KB	Output is correct
23	Correct	300 ms	10052 KB	Output is correct
24	Correct	1216 ms	5828 KB	Output is correct
25	Correct	2132 ms	10052 KB	Output is correct
26	Correct	1864 ms	10052 KB	Output is correct
27	Correct	1704 ms	10052 KB	Output is correct
28	Correct	692 ms	35660 KB	Output is correct
29	Correct	2668 ms	35264 KB	Output is correct
30	Correct	6156 ms	29984 KB	Output is correct
31	Correct	5364 ms	22856 KB	Output is correct
32	Correct	580 ms	1340 KB	Output is correct
33	Correct	768 ms	2000 KB	Output is correct
34	Correct	424 ms	35264 KB	Output is correct
35	Correct	1664 ms	18104 KB	Output is correct
36	Correct	3100 ms	35264 KB	Output is correct
37	Correct	2468 ms	35264 KB	Output is correct
38	Correct	2476 ms	35264 KB	Output is correct
39	Correct	960 ms	76316 KB	Output is correct
40	Correct	4132 ms	75260 KB	Output is correct
41	Correct	8452 ms	63116 KB	Output is correct
42	Correct	7636 ms	47804 KB	Output is correct
43	Correct	808 ms	75260 KB	Output is correct
44	Correct	764 ms	1472 KB	Output is correct
45	Correct	2172 ms	27212 KB	Output is correct
46	Correct	4204 ms	75392 KB	Output is correct
47	Correct	4056 ms	75392 KB	Output is correct
48	Correct	3968 ms	75260 KB	Output is correct
49	Correct	0 ms	1208 KB	Output is correct

Submission #4624

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