답안 #4622 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4622	2013-11-11T11:26:38 Z	cki86201	게임 (IOI13_game)	C++	63 / 100	3060 ms	256000 KB

game

#include "game.h"
#include<stdlib.h>
//for 80point;

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{
	ll x;
	node1 *left,*right;
	void update(int u,int s,int d,ll K){
		if(s==d){x=K;return;}
		int m=(s+d)>>1;
		if(u<=m){
			if(!left)left=(node1 *)calloc(1,sizeof(node1));
			left->update(u,s,m,K);
		}
		else{
			if(!right)right=(node1 *)calloc(1,sizeof(node1));
			right->update(u,m+1,d,K);
		}
		if(right&&left)x=gc(right->x,left->x);
		else if(right)x=right->x;
		else x=left->x;
	}
	ll read(int l,int r,int s,int d){
		if(l<=s&&d<=r)return x;
		if(r<s||d<l)return 0;
		int m=(s+d)>>1;
		if(right&&left)return gc(left->read(l,r,s,m),right->read(l,r,m+1,d));
		if(right)return right->read(l,r,m+1,d);
		if(left)return left->read(l,r,s,m);
		return 0;
	}
	void Union(int r,node1 A,node1 B,int s,int d){
		x=gc(A.x,B.x);
		if(s==d)return;
		int m=(s+d)>>1;
		if(r<=m){
			if(!left)left=(node1 *)calloc(1,sizeof(node1));
			if(A.left&&B.left)left->Union(r,*(A.left),*(B.left),s,m);
			else if(A.left)left->Copy(r,*(A.left),s,m);
			else left->Copy(r,*(B.left),s,m);
		}
		else{
			if(!right)right=(node1 *)calloc(1,sizeof(node1));
			if(A.right&&B.right)right->Union(r,*(A.right),*(B.right),m+1,d);
			else if(A.right)right->Copy(r,*(A.right),m+1,d);
			else right->Copy(r,*(B.right),m+1,d);
		}
	}
	void Copy(int r,node1 A,int s,int d){
		if(s==d){x=A.x;return;}
		int m=(s+d)>>1;
		if(r<=m){
			if(!left)left=(node1 *)calloc(1,sizeof(node1));
			left->Copy(r,*(A.left),s,m);
		}
		else{
			if(!right)right=(node1 *)calloc(1,sizeof(node1));
			right->Copy(r,*(A.right),m+1,d);
		}
		if(right&&left)x=gc(right->x,left->x);
		else if(right)x=right->x;
		else x=left->x;
	}
};

struct node2{
	node1 x;
	node2 *left,*right;
	void update(int u1,int u2,int s,int d,ll K){
		if(s==d){x.update(u2,1,C,K);return;}
		int m=(s+d)>>1;
		if(u1<=m){
			if(!left)left=(node2 *)calloc(1,sizeof(node2));
			left->update(u1,u2,s,m,K);
		}
		else{
			if(!right)right=(node2 *)calloc(1,sizeof(node2));
			right->update(u1,u2,m+1,d,K);
		}
		if(right&&left)x.Union(u2,right->x,left->x,1,C);
		else if(right)x.Copy(u2,right->x,1,C);
		else if(left)x.Copy(u2,left->x,1,C);
	}
	ll read(int l1,int r1,int l2,int r2,int s,int d){
		if(l1<=s&&d<=r1)return x.read(l2,r2,1,C);
		if(r1<s||d<l1)return 0;
		int m=(s+d)>>1;
		if(right&&left)return gc(left->read(l1,r1,l2,r2,s,m),right->read(l1,r1,l2,r2,m+1,d));
		if(right)return right->read(l1,r1,l2,r2,m+1,d);
		if(left)return left->read(l1,r1,l2,r2,s,m);
		return 0;
	}
}tree;

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

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

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

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1108 KB	Output is correct
2	Correct	0 ms	1108 KB	Output is correct
3	Correct	0 ms	1108 KB	Output is correct
4	Correct	832 ms	9292 KB	Output is correct
5	Correct	592 ms	9292 KB	Output is correct
6	Correct	756 ms	9556 KB	Output is correct
7	Correct	840 ms	9556 KB	Output is correct
8	Correct	540 ms	5860 KB	Output is correct
9	Correct	800 ms	9556 KB	Output is correct
10	Correct	712 ms	9556 KB	Output is correct
11	Correct	0 ms	1108 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1108 KB	Output is correct
2	Correct	0 ms	1108 KB	Output is correct
3	Correct	0 ms	1108 KB	Output is correct
4	Correct	0 ms	1108 KB	Output is correct
5	Correct	0 ms	1108 KB	Output is correct
6	Correct	0 ms	1108 KB	Output is correct
7	Correct	0 ms	1108 KB	Output is correct
8	Correct	0 ms	1108 KB	Output is correct
9	Correct	0 ms	1108 KB	Output is correct
10	Correct	0 ms	1108 KB	Output is correct
11	Correct	0 ms	1108 KB	Output is correct
12	Correct	1356 ms	12460 KB	Output is correct
13	Correct	2624 ms	6124 KB	Output is correct
14	Correct	360 ms	1108 KB	Output is correct
15	Correct	3048 ms	8632 KB	Output is correct
16	Correct	308 ms	18136 KB	Output is correct
17	Correct	1284 ms	10876 KB	Output is correct
18	Correct	2024 ms	18136 KB	Output is correct
19	Correct	1784 ms	18136 KB	Output is correct
20	Correct	1696 ms	18136 KB	Output is correct
21	Correct	0 ms	1108 KB	Output is correct

Subtask #4
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1108 KB	Output is correct
2	Correct	0 ms	1108 KB	Output is correct
3	Correct	0 ms	1108 KB	Output is correct
4	Correct	0 ms	1108 KB	Output is correct
5	Correct	0 ms	1108 KB	Output is correct
6	Correct	0 ms	1108 KB	Output is correct
7	Correct	0 ms	1108 KB	Output is correct
8	Correct	0 ms	1108 KB	Output is correct
9	Correct	0 ms	1108 KB	Output is correct
10	Correct	0 ms	1108 KB	Output is correct
11	Correct	0 ms	1108 KB	Output is correct
12	Correct	836 ms	9292 KB	Output is correct
13	Correct	588 ms	9292 KB	Output is correct
14	Correct	740 ms	9556 KB	Output is correct
15	Correct	804 ms	9556 KB	Output is correct
16	Correct	540 ms	5860 KB	Output is correct
17	Correct	784 ms	9556 KB	Output is correct
18	Correct	728 ms	9556 KB	Output is correct
19	Correct	1380 ms	12460 KB	Output is correct
20	Correct	2648 ms	6124 KB	Output is correct
21	Correct	352 ms	1108 KB	Output is correct
22	Correct	3060 ms	8632 KB	Output is correct
23	Correct	284 ms	18136 KB	Output is correct
24	Correct	1264 ms	10876 KB	Output is correct
25	Correct	1992 ms	18136 KB	Output is correct
26	Correct	1780 ms	18136 KB	Output is correct
27	Correct	1712 ms	18136 KB	Output is correct
28	Correct	1128 ms	248476 KB	Output is correct
29	Memory limit exceeded	2480 ms	256000 KB	Memory limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1108 KB	Output is correct
2	Correct	0 ms	1108 KB	Output is correct
3	Correct	0 ms	1108 KB	Output is correct
4	Correct	0 ms	1108 KB	Output is correct
5	Correct	0 ms	1108 KB	Output is correct
6	Correct	0 ms	1108 KB	Output is correct
7	Correct	0 ms	1108 KB	Output is correct
8	Correct	0 ms	1108 KB	Output is correct
9	Correct	0 ms	1108 KB	Output is correct
10	Correct	0 ms	1108 KB	Output is correct
11	Correct	0 ms	1108 KB	Output is correct
12	Correct	836 ms	9292 KB	Output is correct
13	Correct	580 ms	9292 KB	Output is correct
14	Correct	716 ms	9556 KB	Output is correct
15	Correct	812 ms	9556 KB	Output is correct
16	Correct	556 ms	5860 KB	Output is correct
17	Correct	788 ms	9556 KB	Output is correct
18	Correct	724 ms	9556 KB	Output is correct
19	Correct	1364 ms	12460 KB	Output is correct
20	Correct	2644 ms	6124 KB	Output is correct
21	Correct	344 ms	1108 KB	Output is correct
22	Correct	3024 ms	8632 KB	Output is correct
23	Correct	292 ms	18136 KB	Output is correct
24	Correct	1256 ms	10876 KB	Output is correct
25	Correct	2044 ms	18136 KB	Output is correct
26	Correct	1744 ms	18136 KB	Output is correct
27	Correct	1648 ms	18136 KB	Output is correct
28	Correct	1136 ms	248476 KB	Output is correct
29	Memory limit exceeded	2440 ms	256000 KB	Memory limit exceeded
30	Halted	0 ms	0 KB	-

답안 #4622

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0.0 / 17.0

Subtask #5 0.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0.0 / 17.0

Subtask #5
0.0 / 20.0