답안 #7256 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7256	2014-07-28T14:28:06 Z	Rhak	게임 (IOI13_game)	C++	80 / 100	13000 ms	247000 KB

game

#include "game.h"
#include<stdio.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** arr)
	{
		if( p < s || e < p) return;
		else if( p == s && e == p){
			if( N != -1) n->GCD = N;
			else{
				long long fn = 0;
				for(int i = 0; i < 4; i++){
					if(arr[i]) fn = gcd2(fn, arr[i]->read(s,e));
				}
				n->GCD = fn;
			}
			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){
			int mr = ( (long long)s*3 + e) >> 2;
			if( s <= p && p <= mr ){
				if( !n->d[0] ) n->d[0] = new _node(0);
				update(n->d[0], s, mr, p, N, arr);
				t[0] = n->d[0]->GCD;
			}
			for(long long i = 1; i < 4; i++){
				int ml = (( s*(4-i) + e*i) >> 2) + 1;
				int mr = ( s*(3-i) + e*(i+1)) >> 2;
				if( ml <= p && p <= mr ){
					if( !n->d[i] ) n->d[i] = new _node(0);
					update(n->d[i], ml, mr, p, N, arr);
					t[i] = n->d[i]->GCD;
				}
			}
		}
		else{
			for(int j = s, i = 0; j <= e; i++, j++){
				if( j != p) continue;
				if( !n->d[i] ) n->d[i] = new _node(0);
				update(n->d[i], j, j, p, N, arr);
				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)
	{
		_IndexTree* arr[4] = {0};
		update(root, S, E, p, N, arr);
	}

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

	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){
			int mr = ( (long long)s*3 + e) >> 2;
			t = n->d[0]? read(n->d[0], s, mr, p, q):0;
			fn = gcd2(fn, t);
			for(long long i = 1; i < 4; i++){
				int ml = (( s*(4-i) + e*i) >> 2) + 1;
				int mr = ( s*(3-i) + e*(i+1)) >> 2;
				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 *d[4];
	_IndexTree *IT;
	node(int C){
		d[0] = d[1] = d[2] = d[3] = 0;
		IT = new _IndexTree(0, C);
	}
};

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;
		}
		long long t[4] = {0}, fn = 0; 
		if( e >= s+4){
			int mr = ( (long long)s*3 + e) >> 2;
			if( s <= p && p <= mr ){
				if( !n->d[0] ) n->d[0] = new node(C);
				update(n->d[0], s, mr, p, q, N);
			}
			for(long long i = 1; i < 4; i++){
				int ml = (( s*(4-i) + e*i) >> 2) + 1;
				int mr = ( s*(3-i) + e*(i+1)) >> 2;
				if( ml <= p && p <= mr ){
					if( !n->d[i] ) n->d[i] = new node(C);
					update(n->d[i], ml, mr, p, q, N);
				}
			}
		}
		else{
			for(int j = s, i = 0; j <= e; i++, j++){
				if( j != p) continue;
				if( !n->d[i] ) n->d[i] = new node(C);
				update(n->d[i], j, j, p, q, N);
			}
		}
		_IndexTree *arr[4] = {0};
		for(int i = 0; i < 4; i++) arr[i] = n->d[i]? n->d[i]->IT: 0;
		n->IT->update(q, arr);
	}
	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);
		}
		long long t, fn = 0;
		if( e >= s+4){
			int mr = ((long long)s*3 + e) >> 2;
			fn = gcd2(fn, n->d[0]? read(n->d[0], s, mr, p, q, u, v):0);
			for(long long i = 1; i < 4; i++){
				int ml = (( s*(4-i) + e*i) >> 2) + 1;
				int mr = ( s*(3-i) + e*(i+1)) >> 2;
				fn = gcd2(fn, n->d[i]? read(n->d[i], ml, mr, p, q, u, v):0);
			}
		}
		else{
			for(int j = s, i = 0; j <= e; i++, j++){
				t = n->d[i]? read(n->d[i], j, j, p, q, u, v):0;
				fn = gcd2(fn, t);
			}
		}
		return fn;
	}
	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-1);
}

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	1216 KB	Output is correct
3	Correct	1216 KB	Output is correct
4	Correct	1216 KB	Output is correct
5	Correct	1216 KB	Output is correct
6	Correct	1216 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	1252 ms	6364 KB	Output is correct
5	Correct	856 ms	6364 KB	Output is correct
6	Correct	1032 ms	6364 KB	Output is correct
7	Correct	1128 ms	6364 KB	Output is correct
8	Correct	716 ms	3988 KB	Output is correct
9	Correct	1132 ms	6364 KB	Output is correct
10	Correct	980 ms	6364 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	1216 KB	Output is correct
3	Correct	0 ms	1216 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	1216 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	2324 ms	6628 KB	Output is correct
13	Correct	4488 ms	3724 KB	Output is correct
14	Correct	440 ms	1216 KB	Output is correct
15	Correct	5104 ms	6232 KB	Output is correct
16	Correct	316 ms	11380 KB	Output is correct
17	Correct	1852 ms	6892 KB	Output is correct
18	Correct	3100 ms	11380 KB	Output is correct
19	Correct	2672 ms	11380 KB	Output is correct
20	Correct	2500 ms	11380 KB	Output is correct
21	Correct	0 ms	1216 KB	Output is correct

Subtask #4
17.0 / 17.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	0 ms	1216 KB	Output is correct
5	Correct	0 ms	1216 KB	Output is correct
6	Correct	0 ms	1216 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	1252 ms	6364 KB	Output is correct
13	Correct	868 ms	6364 KB	Output is correct
14	Correct	1016 ms	6364 KB	Output is correct
15	Correct	1156 ms	6364 KB	Output is correct
16	Correct	700 ms	3988 KB	Output is correct
17	Correct	1116 ms	6364 KB	Output is correct
18	Correct	956 ms	6364 KB	Output is correct
19	Correct	2296 ms	6628 KB	Output is correct
20	Correct	4500 ms	3724 KB	Output is correct
21	Correct	452 ms	1216 KB	Output is correct
22	Correct	5044 ms	6232 KB	Output is correct
23	Correct	312 ms	11380 KB	Output is correct
24	Correct	1892 ms	6892 KB	Output is correct
25	Correct	3148 ms	11380 KB	Output is correct
26	Correct	2680 ms	11380 KB	Output is correct
27	Correct	2520 ms	11380 KB	Output is correct
28	Correct	1076 ms	106420 KB	Output is correct
29	Correct	3608 ms	115396 KB	Output is correct
30	Correct	10520 ms	84772 KB	Output is correct
31	Correct	9672 ms	64840 KB	Output is correct
32	Correct	784 ms	1348 KB	Output is correct
33	Correct	1164 ms	2536 KB	Output is correct
34	Correct	640 ms	115396 KB	Output is correct
35	Correct	2416 ms	58636 KB	Output is correct
36	Correct	4248 ms	115396 KB	Output is correct
37	Correct	3572 ms	115396 KB	Output is correct
38	Correct	3488 ms	115396 KB	Output is correct
39	Correct	3432 ms	88732 KB	Output is correct
40	Correct	0 ms	1216 KB	Output is correct

Subtask #5
0.0 / 20.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	0 ms	1216 KB	Output is correct
5	Correct	0 ms	1216 KB	Output is correct
6	Correct	0 ms	1216 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	1280 ms	6364 KB	Output is correct
13	Correct	888 ms	6364 KB	Output is correct
14	Correct	1044 ms	6364 KB	Output is correct
15	Correct	1160 ms	6364 KB	Output is correct
16	Correct	732 ms	3988 KB	Output is correct
17	Correct	1136 ms	6364 KB	Output is correct
18	Correct	960 ms	6364 KB	Output is correct
19	Correct	2328 ms	6628 KB	Output is correct
20	Correct	4512 ms	3724 KB	Output is correct
21	Correct	464 ms	1216 KB	Output is correct
22	Correct	5072 ms	6232 KB	Output is correct
23	Correct	324 ms	11380 KB	Output is correct
24	Correct	1896 ms	6892 KB	Output is correct
25	Correct	3112 ms	11380 KB	Output is correct
26	Correct	2700 ms	11380 KB	Output is correct
27	Correct	2468 ms	11380 KB	Output is correct
28	Correct	1112 ms	106420 KB	Output is correct
29	Correct	3612 ms	115396 KB	Output is correct
30	Correct	10500 ms	84772 KB	Output is correct
31	Correct	9684 ms	64840 KB	Output is correct
32	Correct	784 ms	1348 KB	Output is correct
33	Correct	1160 ms	2536 KB	Output is correct
34	Correct	612 ms	115396 KB	Output is correct
35	Correct	2364 ms	58636 KB	Output is correct
36	Correct	4256 ms	115396 KB	Output is correct
37	Correct	3532 ms	115396 KB	Output is correct
38	Correct	3488 ms	115396 KB	Output is correct
39	Correct	1596 ms	223372 KB	Output is correct
40	Correct	5464 ms	247000 KB	Output is correct
41	Execution timed out	13000 ms	174928 KB	Program timed out
42	Halted	0 ms	0 KB	-

답안 #7256

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.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
17.0 / 17.0

Subtask #5
0.0 / 20.0