답안 #4635 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4635	2013-11-13T11:55:12 Z	ainta	게임 (IOI13_game)	C++	63 / 100	3736 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;

	node->G=0;
	if(m >= y){
		if(!node->c1)node->c1 = new Y_Seg(node->b,m);
		update_Y(node->c1, y, K);
	}
	else{
		if(!node->c2)node->c2 = new Y_Seg(m+1,node->e);
		update_Y(node->c2, y, K);
	}
	node->G=gcd2(node->c1?node->c1->G:0,node->c2?node->c2->G:0);
}

void update_XY(X_Seg *node, int y){
	Y_Seg *n1=node->c1?node->c1->cy:NULL, *n2=node->c2?node->c2->cy:NULL, *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(m>=y){
			if(!cur->c1)cur->c1=new Y_Seg(cur->b,m);
			cur=cur->c1;
			if(n1)n1=n1->c1;
			if(n2)n2=n2->c1;
		}
		else{
			if(!cur->c2)cur->c2=new Y_Seg(m+1,cur->e);
			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->cy)node->cy = new Y_Seg(0,M-1);
	if(m >= x){
		if(!node->c1)node->c1 = new X_Seg(node->b,m);
		update_X(node->c1, x, y, K);
	}
	else{
		if(!node->c2)node->c2 = new X_Seg(m+1,node->e);
		update_X(node->c2, 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	1340 KB	Output is correct
3	Correct	1340 KB	Output is correct
4	Correct	1208 KB	Output is correct
5	Correct	1208 KB	Output is correct
6	Correct	1340 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	880 ms	13616 KB	Output is correct
5	Correct	532 ms	13616 KB	Output is correct
6	Correct	808 ms	13880 KB	Output is correct
7	Correct	920 ms	13880 KB	Output is correct
8	Correct	556 ms	8336 KB	Output is correct
9	Correct	876 ms	13880 KB	Output is correct
10	Correct	748 ms	13880 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	1340 KB	Output is correct
3	Correct	0 ms	1340 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	1340 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	1396 ms	18368 KB	Output is correct
13	Correct	3144 ms	8864 KB	Output is correct
14	Correct	392 ms	1340 KB	Output is correct
15	Correct	3736 ms	12692 KB	Output is correct
16	Correct	288 ms	26948 KB	Output is correct
17	Correct	1412 ms	15992 KB	Output is correct
18	Correct	2316 ms	26948 KB	Output is correct
19	Correct	2008 ms	26948 KB	Output is correct
20	Correct	1828 ms	26948 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	1340 KB	Output is correct
3	Correct	0 ms	1340 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	1340 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	868 ms	13616 KB	Output is correct
13	Correct	528 ms	13616 KB	Output is correct
14	Correct	804 ms	13880 KB	Output is correct
15	Correct	876 ms	13880 KB	Output is correct
16	Correct	560 ms	8336 KB	Output is correct
17	Correct	860 ms	13880 KB	Output is correct
18	Correct	724 ms	13880 KB	Output is correct
19	Correct	1368 ms	18368 KB	Output is correct
20	Correct	3120 ms	8864 KB	Output is correct
21	Correct	392 ms	1340 KB	Output is correct
22	Correct	3728 ms	12692 KB	Output is correct
23	Correct	276 ms	26948 KB	Output is correct
24	Correct	1408 ms	15992 KB	Output is correct
25	Correct	2284 ms	26948 KB	Output is correct
26	Correct	1992 ms	26948 KB	Output is correct
27	Correct	1852 ms	26948 KB	Output is correct
28	Memory limit exceeded	736 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	1340 KB	Output is correct
3	Correct	0 ms	1340 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	1340 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	892 ms	13616 KB	Output is correct
13	Correct	508 ms	13616 KB	Output is correct
14	Correct	784 ms	13880 KB	Output is correct
15	Correct	872 ms	13880 KB	Output is correct
16	Correct	560 ms	8336 KB	Output is correct
17	Correct	852 ms	13880 KB	Output is correct
18	Correct	736 ms	13880 KB	Output is correct
19	Correct	1372 ms	18368 KB	Output is correct
20	Correct	3128 ms	8864 KB	Output is correct
21	Correct	388 ms	1340 KB	Output is correct
22	Correct	3708 ms	12692 KB	Output is correct
23	Correct	292 ms	26948 KB	Output is correct
24	Correct	1388 ms	15992 KB	Output is correct
25	Correct	2300 ms	26948 KB	Output is correct
26	Correct	1972 ms	26948 KB	Output is correct
27	Correct	1816 ms	26948 KB	Output is correct
28	Memory limit exceeded	712 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

답안 #4635

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