답안 #7237 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7237	2014-07-28T12:22:33 Z	Rhak	게임 (IOI13_game)	C++	63 / 100	3256 ms	256000 KB

game

#include "game.h"

long long gcd2(long long x, long long y){ return y==0? x: gcd2(y, x%y); }

struct _node{
	_node *left, *right;
	long long GCD;
	_node(long long GCD):GCD(GCD){ left = right = 0; }
};

struct _IndexTree{
	int S, E;
	_node *root;
	_IndexTree(int S,int E):S(S), E(E){ root = new _node(0);}
	void update(_node* n, int s, int e, int p, long long N, _IndexTree* l, _IndexTree* r)
	{
		if( p < s || e < p) return;
		else if( p == s && e == p){
			if( N != -1) n->GCD = N;
			else n->GCD = gcd2(l?l->read(s, e):0, r?r->read(s, e):0);
			return;
		}
		int m = (s+e) >> 1;
		long long t1 = n->left? n->left->GCD:0, t2 = n->right? n->right->GCD:0;
		if( p <= m ){
			if( !n->left ) n->left = new _node(0);
			update(n->left, s, m, p, N, l, r);
			t1 = n->left->GCD;
		}
		else{
			if( !n->right ) n->right = new _node(0);
			update(n->right, m+1, e, p, N, l, r);
			t2 = n->right->GCD;
		}
		n->GCD = gcd2(t1,t2);
	}
	void update(int p, long long N)
	{
		update(root, S, E, p, N, 0, 0);
	}

	void update(int p, _IndexTree* l, _IndexTree* r)
	{
		update(root, S, E, p, -1, l, r);
	}

	long long read(_node *n, int s, int e, int p, int q)
	{
		if( !n ) return 0;
		if( q < s || e < p) return 0;
		else if( p <= s && e <= q){
			return n->GCD;
		}
		int m = (s+e) >> 1;
		long long t1 = n->left? read(n->left, s, m, p, q):0;
		long long t2 = n->right? read(n->right, m+1, e, p, q):0;
		return gcd2(t1, t2);
	}

	long long read(int s,int e){
		return read(root, S, E, s, e);
	}
};

struct node{
	node *left, *right;
	_IndexTree *IT;
	node(int C){
		left = right = 0;
		IT = new _IndexTree(0, C-1);
	}
};

struct IndexTree{
	int S, E, C;
	node* root;
	IndexTree(int S, int E, int C):S(S), E(E), C(C){
		root = new node(C);
	}
	
	void update(node* n, int s, int e, int p, int q, long long N)
	{
		if( p < s || e < p) return;	
		if( p == s && e == p){
			n->IT->update(q, N);
			return;
		}
		int m = (s+e) >> 1;
		if( p <= m ){
			if( !n->left ) n->left = new node(C);
			update(n->left, s, m, p, q, N);
		}
		else{
			if( !n->right ) n->right = new node(C);
			update(n->right, m+1, e, p, q, N);
		}
		n->IT->update(q, n->left? n->left->IT : 0, n->right? n->right->IT : 0);
	}
	void update(int p, int q, long long N)
	{
		update(root, S, E, p, q, N);
	}

	long long read(node *n, int s, int e, int p, int q, int u, int v)
	{
		if( !n ) return 0;
		if( q < s || e < p) return 0;
		else if( p <= s && e <= q){
			return n->IT->read(u, v);
		}
		int m = (s+e) >> 1;
		long long t1 = n->left? read(n->left, s, m, p, q, u, v):0;
		long long t2 = n->right? read(n->right, m+1, e, p, q, u, v):0;
		return gcd2(t1, t2);
	}
	long long read(int P,int Q,int U, int V)
	{
		return read(root, S, E, P, Q, U, V);
	}
}*IT;

void init(int R, int C){
	IT = new IndexTree(0, R-1, C);
}

void update(int R, int C, long long K){
	IT->update(R, C, K);
}

long long calculate(int P, int Q, int U, int V){
	return IT->read(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1224 KB	Output is correct
2	Correct	0 ms	1224 KB	Output is correct
3	Correct	0 ms	1224 KB	Output is correct
4	Correct	904 ms	9408 KB	Output is correct
5	Correct	648 ms	9408 KB	Output is correct
6	Correct	804 ms	9672 KB	Output is correct
7	Correct	896 ms	9672 KB	Output is correct
8	Correct	580 ms	5976 KB	Output is correct
9	Correct	892 ms	9672 KB	Output is correct
10	Correct	768 ms	9672 KB	Output is correct
11	Correct	0 ms	1224 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1224 KB	Output is correct
2	Correct	0 ms	1224 KB	Output is correct
3	Correct	0 ms	1224 KB	Output is correct
4	Correct	0 ms	1224 KB	Output is correct
5	Correct	0 ms	1224 KB	Output is correct
6	Correct	0 ms	1224 KB	Output is correct
7	Correct	0 ms	1224 KB	Output is correct
8	Correct	0 ms	1224 KB	Output is correct
9	Correct	0 ms	1224 KB	Output is correct
10	Correct	0 ms	1224 KB	Output is correct
11	Correct	0 ms	1224 KB	Output is correct
12	Correct	1508 ms	12708 KB	Output is correct
13	Correct	2772 ms	6372 KB	Output is correct
14	Correct	452 ms	1356 KB	Output is correct
15	Correct	3244 ms	8880 KB	Output is correct
16	Correct	356 ms	18516 KB	Output is correct
17	Correct	1412 ms	11124 KB	Output is correct
18	Correct	2252 ms	18516 KB	Output is correct
19	Correct	1996 ms	18516 KB	Output is correct
20	Correct	1876 ms	18516 KB	Output is correct
21	Correct	0 ms	1224 KB	Output is correct

Subtask #4
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1224 KB	Output is correct
2	Correct	0 ms	1224 KB	Output is correct
3	Correct	0 ms	1224 KB	Output is correct
4	Correct	0 ms	1224 KB	Output is correct
5	Correct	0 ms	1224 KB	Output is correct
6	Correct	0 ms	1224 KB	Output is correct
7	Correct	0 ms	1224 KB	Output is correct
8	Correct	0 ms	1224 KB	Output is correct
9	Correct	0 ms	1224 KB	Output is correct
10	Correct	0 ms	1224 KB	Output is correct
11	Correct	0 ms	1224 KB	Output is correct
12	Correct	912 ms	9408 KB	Output is correct
13	Correct	640 ms	9408 KB	Output is correct
14	Correct	816 ms	9672 KB	Output is correct
15	Correct	912 ms	9672 KB	Output is correct
16	Correct	576 ms	5976 KB	Output is correct
17	Correct	868 ms	9672 KB	Output is correct
18	Correct	776 ms	9672 KB	Output is correct
19	Correct	1536 ms	12708 KB	Output is correct
20	Correct	2800 ms	6372 KB	Output is correct
21	Correct	428 ms	1356 KB	Output is correct
22	Correct	3256 ms	8880 KB	Output is correct
23	Correct	360 ms	18516 KB	Output is correct
24	Correct	1420 ms	11124 KB	Output is correct
25	Correct	2312 ms	18516 KB	Output is correct
26	Correct	2012 ms	18516 KB	Output is correct
27	Correct	1864 ms	18516 KB	Output is correct
28	Memory limit exceeded	1436 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1224 KB	Output is correct
2	Correct	0 ms	1224 KB	Output is correct
3	Correct	0 ms	1224 KB	Output is correct
4	Correct	0 ms	1224 KB	Output is correct
5	Correct	0 ms	1224 KB	Output is correct
6	Correct	0 ms	1224 KB	Output is correct
7	Correct	0 ms	1224 KB	Output is correct
8	Correct	0 ms	1224 KB	Output is correct
9	Correct	0 ms	1224 KB	Output is correct
10	Correct	0 ms	1224 KB	Output is correct
11	Correct	0 ms	1224 KB	Output is correct
12	Correct	904 ms	9408 KB	Output is correct
13	Correct	664 ms	9408 KB	Output is correct
14	Correct	808 ms	9672 KB	Output is correct
15	Correct	908 ms	9672 KB	Output is correct
16	Correct	592 ms	5976 KB	Output is correct
17	Correct	880 ms	9672 KB	Output is correct
18	Correct	784 ms	9672 KB	Output is correct
19	Correct	1500 ms	12708 KB	Output is correct
20	Correct	2772 ms	6372 KB	Output is correct
21	Correct	424 ms	1356 KB	Output is correct
22	Correct	3220 ms	8880 KB	Output is correct
23	Correct	332 ms	18516 KB	Output is correct
24	Correct	1412 ms	11124 KB	Output is correct
25	Correct	2280 ms	18516 KB	Output is correct
26	Correct	2044 ms	18516 KB	Output is correct
27	Correct	1856 ms	18516 KB	Output is correct
28	Memory limit exceeded	1380 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

답안 #7237

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