답안 #4631 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4631	2013-11-13T11:32:12 Z	ainta	게임 (IOI13_game)	C++	63 / 100	3660 ms	256000 KB

game

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

int N,M;

struct Y_Seg{
	Y_Seg *c1, *c2;
	int b,e;
	long long G;
	Y_Seg(int p,int q){
		c1=NULL,c2=NULL,G=0;
		b=p,e=q;
	}
};

struct X_Seg{
	X_Seg *c1, *c2;
	Y_Seg *cy;
	int b,e;
	X_Seg(int p,int q){
		c1=NULL,c2=NULL,cy=NULL;
		b=p,e=q;
	}
};
X_Seg *root;

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;
}

void init(int R, int C) {
	N=R,M=C;
	root = new X_Seg(0,N-1);
}

void update_Y(Y_Seg *node, int y, long long K){
	if(node->b==node->e){
		node->G=K;
		return;
	}
	int m = (node->b+node->e)>>1;

	if(!node->c1)node->c1 = new Y_Seg(node->b,m);
	if(!node->c2)node->c2 = new Y_Seg(m+1,node->e);
	
	if(m < y)update_Y(node->c2, y, K);
	else update_Y(node->c1, y, K);

	node->G=gcd2(node->c1->G,node->c2->G);
}

void update_XY(X_Seg *node, int y){
	Y_Seg *n1=node->c1->cy, *n2=node->c2->cy, *cur=node->cy;
	int m;
	while(n1 || n2){
		cur->G = gcd2(n1?n1->G:0,n2?n2->G:0);
		if(cur->b==cur->e)break;
		m=(cur->b+cur->e)>>1;
		if(!cur->c1)cur->c1=new Y_Seg(cur->b,m);
		if(!cur->c2)cur->c2=new Y_Seg(m+1,cur->e);
		if(m>=y){
			cur=cur->c1;
			if(n1)n1=n1->c1;
			if(n2)n2=n2->c1;
		}
		else{
			cur=cur->c2;
			if(n1)n1=n1->c2;
			if(n2)n2=n2->c2;
		}
	}
}

void update_X(X_Seg *node, int x, int y, long long K){
	if(node->b==node->e){
		if(node->cy==NULL)node->cy = new Y_Seg(0,M-1);
		update_Y(node->cy, y, K);
		return;
	}
	int m = (node->b+node->e)>>1;

	if(!node->c1)node->c1 = new X_Seg(node->b,m);
	if(!node->c2)node->c2 = new X_Seg(m+1,node->e);
	if(!node->cy)node->cy = new Y_Seg(0,M-1);

	if(m < x)update_X(node->c2, x, y, K);
	else update_X(node->c1, x, y, K);

	update_XY(node, y);
}

void update(int P, int Q, long long K) {
	update_X(root,P,Q,K);
}

long long CalcY(Y_Seg *node, int s,int l){
	if(s==node->b && l==node->e){
		return node->G;
	}
	int m = (node->b + node->e) >>1;
	long long G=0;
	if(s <= m){
		if(node->c1){
			G=CalcY(node->c1,s,min(l,m));
		}
	}
	if(l > m){
		if(node->c2){
			G=gcd2(G,CalcY(node->c2,max(m+1,s),l));
		}
	}
	return G;
}

long long CalcX(X_Seg *node, int P,int Q,int U,int V){
	if(P==node->b && U==node->e){
		if(node->cy)return CalcY(node->cy,Q,V);
		return 0;
	}
	int m = (node->b + node->e) >>1;
	long long G=0;
	if(P <= m){
		if(node->c1){
			G=CalcX(node->c1,P,Q,min(U,m),V);
		}
	}
	if(U > m){
		if(node->c2){
			G=gcd2(G,CalcX(node->c2,max(m+1,P),Q,U,V));
		}
	}
	return G;
}

long long calculate(int P, int Q, int U, int V) {
	return CalcX(root,P,Q,U,V);
}

Subtask #1
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	1208 KB	Output is correct
2	Correct	1472 KB	Output is correct
3	Correct	1472 KB	Output is correct
4	Correct	1208 KB	Output is correct
5	Correct	1208 KB	Output is correct
6	Correct	1472 KB	Output is correct
7	Correct	1208 KB	Output is correct
8	Correct	1208 KB	Output is correct
9	Correct	1340 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	968 ms	22064 KB	Output is correct
5	Correct	572 ms	22064 KB	Output is correct
6	Correct	844 ms	22592 KB	Output is correct
7	Correct	940 ms	22592 KB	Output is correct
8	Correct	600 ms	13484 KB	Output is correct
9	Correct	920 ms	22592 KB	Output is correct
10	Correct	816 ms	22460 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	1472 KB	Output is correct
3	Correct	0 ms	1472 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	1472 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	1340 KB	Output is correct
10	Correct	0 ms	1208 KB	Output is correct
11	Correct	0 ms	1208 KB	Output is correct
12	Correct	1480 ms	28268 KB	Output is correct
13	Correct	3064 ms	12560 KB	Output is correct
14	Correct	444 ms	1472 KB	Output is correct
15	Correct	3648 ms	19028 KB	Output is correct
16	Correct	300 ms	43712 KB	Output is correct
17	Correct	1652 ms	26156 KB	Output is correct
18	Correct	2512 ms	43712 KB	Output is correct
19	Correct	2276 ms	43844 KB	Output is correct
20	Correct	2124 ms	43712 KB	Output is correct
21	Correct	0 ms	1208 KB	Output is correct

Subtask #4
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1208 KB	Output is correct
2	Correct	0 ms	1472 KB	Output is correct
3	Correct	0 ms	1472 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	1472 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	1340 KB	Output is correct
10	Correct	0 ms	1208 KB	Output is correct
11	Correct	0 ms	1208 KB	Output is correct
12	Correct	952 ms	22064 KB	Output is correct
13	Correct	596 ms	22064 KB	Output is correct
14	Correct	832 ms	22592 KB	Output is correct
15	Correct	916 ms	22592 KB	Output is correct
16	Correct	624 ms	13484 KB	Output is correct
17	Correct	912 ms	22592 KB	Output is correct
18	Correct	788 ms	22460 KB	Output is correct
19	Correct	1464 ms	28268 KB	Output is correct
20	Correct	3012 ms	12560 KB	Output is correct
21	Correct	420 ms	1472 KB	Output is correct
22	Correct	3660 ms	19028 KB	Output is correct
23	Correct	332 ms	43712 KB	Output is correct
24	Correct	1540 ms	26156 KB	Output is correct
25	Correct	2508 ms	43712 KB	Output is correct
26	Correct	2208 ms	43844 KB	Output is correct
27	Correct	2092 ms	43712 KB	Output is correct
28	Memory limit exceeded	512 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1208 KB	Output is correct
2	Correct	0 ms	1472 KB	Output is correct
3	Correct	0 ms	1472 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	1472 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	1340 KB	Output is correct
10	Correct	0 ms	1208 KB	Output is correct
11	Correct	0 ms	1208 KB	Output is correct
12	Correct	896 ms	22064 KB	Output is correct
13	Correct	576 ms	22064 KB	Output is correct
14	Correct	816 ms	22592 KB	Output is correct
15	Correct	920 ms	22592 KB	Output is correct
16	Correct	588 ms	13484 KB	Output is correct
17	Correct	896 ms	22592 KB	Output is correct
18	Correct	820 ms	22460 KB	Output is correct
19	Correct	1468 ms	28268 KB	Output is correct
20	Correct	3044 ms	12560 KB	Output is correct
21	Correct	428 ms	1472 KB	Output is correct
22	Correct	3644 ms	19028 KB	Output is correct
23	Correct	324 ms	43712 KB	Output is correct
24	Correct	1608 ms	26156 KB	Output is correct
25	Correct	2560 ms	43712 KB	Output is correct
26	Correct	2232 ms	43844 KB	Output is correct
27	Correct	2052 ms	43712 KB	Output is correct
28	Memory limit exceeded	408 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

답안 #4631

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