답안 #7240 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7240	2014-07-28T12:49:58 Z	Rhak	게임 (IOI13_game)	C++	63 / 100	4492 ms	134404 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 *d[4];
	long long GCD;
	_node(long long GCD):GCD(GCD){ d[0] = d[1] = d[2] = d[3] = 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;
		}
		long long t[4] = {0}, fn = 0; 
		for(int i = 0; i < 4; i++) t[i] = n->d[i]? n->d[i]->GCD:0;
		if( e >= s+4){
			for(int i = 0; i < 4; i++){
				int ml = (( s*(4-i) + e*i) >> 2) + 1;
				int mr = ( s*(3-i) + e*(i+1)) >> 2;
				if(i == 0) ml--;
				if( ml <= p && p <= mr ){
					if( !n->d[i] ) n->d[i] = new _node(0);
					update(n->d[i], ml, mr, p, N, l, r);
					t[i] = n->d[i]->GCD;
				}
			}
		}
		else{
			for(int j = s, i = 0; j <= e; i++, j++){
				if( !n->d[i] ) n->d[i] = new _node(0);
				update(n->d[i], j, j, p, N, l, r);
				t[i] = n->d[i]->GCD;
			}
		}		
		for(int i = 0; i < 4; i ++) fn = gcd2(fn, t[i]);
		n->GCD = fn;
	}
	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 t , fn = 0;
		if( e >= s+4){
			for(int i = 0; i < 4; i++){
				int ml = (( s*(4-i) + e*i) >> 2) + 1;
				int mr = ( s*(3-i) + e*(i+1)) >> 2;
				if(i == 0) ml--;
				t = n->d[i]? read(n->d[i], ml, mr, p, q):0;
				fn = gcd2(fn, t);
			}
		}
		else{
			for(int j = s, i = 0; j <= e; i++, j++){
				t = n->d[i]? read(n->d[i], j, j, p, q):0;
				fn = gcd2(fn, t);
			}
		}		
		return fn;
	}

	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	1216 KB	Output is correct
2	Correct	1348 KB	Output is correct
3	Correct	1348 KB	Output is correct
4	Correct	1216 KB	Output is correct
5	Correct	1216 KB	Output is correct
6	Correct	1348 KB	Output is correct
7	Correct	1216 KB	Output is correct
8	Correct	1216 KB	Output is correct
9	Correct	1216 KB	Output is correct
10	Correct	1216 KB	Output is correct
11	Correct	1216 KB	Output is correct
12	Correct	1216 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1216 KB	Output is correct
2	Correct	0 ms	1216 KB	Output is correct
3	Correct	0 ms	1216 KB	Output is correct
4	Correct	1224 ms	9928 KB	Output is correct
5	Correct	892 ms	9928 KB	Output is correct
6	Correct	1032 ms	10060 KB	Output is correct
7	Correct	1128 ms	10060 KB	Output is correct
8	Correct	684 ms	5968 KB	Output is correct
9	Correct	1100 ms	10060 KB	Output is correct
10	Correct	952 ms	10060 KB	Output is correct
11	Correct	0 ms	1216 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1216 KB	Output is correct
2	Correct	0 ms	1348 KB	Output is correct
3	Correct	0 ms	1348 KB	Output is correct
4	Correct	0 ms	1216 KB	Output is correct
5	Correct	0 ms	1216 KB	Output is correct
6	Correct	4 ms	1348 KB	Output is correct
7	Correct	0 ms	1216 KB	Output is correct
8	Correct	0 ms	1216 KB	Output is correct
9	Correct	0 ms	1216 KB	Output is correct
10	Correct	0 ms	1216 KB	Output is correct
11	Correct	0 ms	1216 KB	Output is correct
12	Correct	2052 ms	17848 KB	Output is correct
13	Correct	3980 ms	8212 KB	Output is correct
14	Correct	480 ms	1348 KB	Output is correct
15	Correct	4492 ms	10456 KB	Output is correct
16	Correct	372 ms	21016 KB	Output is correct
17	Correct	1676 ms	12304 KB	Output is correct
18	Correct	2744 ms	21016 KB	Output is correct
19	Correct	2440 ms	21016 KB	Output is correct
20	Correct	2212 ms	21016 KB	Output is correct
21	Correct	0 ms	1216 KB	Output is correct

Subtask #4
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1216 KB	Output is correct
2	Correct	0 ms	1348 KB	Output is correct
3	Correct	0 ms	1348 KB	Output is correct
4	Correct	0 ms	1216 KB	Output is correct
5	Correct	0 ms	1216 KB	Output is correct
6	Correct	0 ms	1348 KB	Output is correct
7	Correct	0 ms	1216 KB	Output is correct
8	Correct	0 ms	1216 KB	Output is correct
9	Correct	0 ms	1216 KB	Output is correct
10	Correct	0 ms	1216 KB	Output is correct
11	Correct	0 ms	1216 KB	Output is correct
12	Correct	1192 ms	9928 KB	Output is correct
13	Correct	880 ms	9928 KB	Output is correct
14	Correct	1004 ms	10060 KB	Output is correct
15	Correct	1128 ms	10060 KB	Output is correct
16	Correct	704 ms	5968 KB	Output is correct
17	Correct	1088 ms	10060 KB	Output is correct
18	Correct	996 ms	10060 KB	Output is correct
19	Correct	2136 ms	17848 KB	Output is correct
20	Correct	3904 ms	8212 KB	Output is correct
21	Correct	472 ms	1348 KB	Output is correct
22	Correct	4484 ms	10456 KB	Output is correct
23	Correct	340 ms	21016 KB	Output is correct
24	Correct	1700 ms	12304 KB	Output is correct
25	Correct	2796 ms	21016 KB	Output is correct
26	Correct	2480 ms	21016 KB	Output is correct
27	Correct	2312 ms	21016 KB	Output is correct
28	Incorrect	980 ms	134404 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1216 KB	Output is correct
2	Correct	0 ms	1348 KB	Output is correct
3	Correct	0 ms	1348 KB	Output is correct
4	Correct	0 ms	1216 KB	Output is correct
5	Correct	0 ms	1216 KB	Output is correct
6	Correct	0 ms	1348 KB	Output is correct
7	Correct	0 ms	1216 KB	Output is correct
8	Correct	0 ms	1216 KB	Output is correct
9	Correct	0 ms	1216 KB	Output is correct
10	Correct	0 ms	1216 KB	Output is correct
11	Correct	0 ms	1216 KB	Output is correct
12	Correct	1224 ms	9928 KB	Output is correct
13	Correct	904 ms	9928 KB	Output is correct
14	Correct	996 ms	10060 KB	Output is correct
15	Correct	1116 ms	10060 KB	Output is correct
16	Correct	720 ms	5968 KB	Output is correct
17	Correct	1072 ms	10060 KB	Output is correct
18	Correct	948 ms	10060 KB	Output is correct
19	Correct	2092 ms	17848 KB	Output is correct
20	Correct	3840 ms	8212 KB	Output is correct
21	Correct	468 ms	1348 KB	Output is correct
22	Correct	4448 ms	10456 KB	Output is correct
23	Correct	360 ms	21016 KB	Output is correct
24	Correct	1664 ms	12304 KB	Output is correct
25	Correct	2728 ms	21016 KB	Output is correct
26	Correct	2372 ms	21016 KB	Output is correct
27	Correct	2228 ms	21016 KB	Output is correct
28	Incorrect	992 ms	134404 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #7240

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