답안 #4624

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4624 2013-11-13T02:50:55 Z cki86201 게임 (IOI13_game) C++
100 / 100
8452 ms 76316 KB
#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);
}
# 결과 실행 시간 메모리 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 0 ms 1208 KB Output is correct
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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