답안 #7255 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7255	2014-07-28T14:11:22 Z	Rhak	게임 (IOI13_game)	C++	63 / 100	5048 ms	55864 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 = ( 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 = ( 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 = ( 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 = (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	1248 ms	6364 KB	Output is correct
5	Correct	860 ms	6364 KB	Output is correct
6	Correct	1004 ms	6364 KB	Output is correct
7	Correct	1144 ms	6364 KB	Output is correct
8	Correct	708 ms	3988 KB	Output is correct
9	Correct	1116 ms	6364 KB	Output is correct
10	Correct	940 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	2320 ms	6628 KB	Output is correct
13	Correct	4476 ms	3724 KB	Output is correct
14	Correct	440 ms	1216 KB	Output is correct
15	Correct	5024 ms	6232 KB	Output is correct
16	Correct	296 ms	11380 KB	Output is correct
17	Correct	1828 ms	6892 KB	Output is correct
18	Correct	3104 ms	11380 KB	Output is correct
19	Correct	2668 ms	11380 KB	Output is correct
20	Correct	2560 ms	11380 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	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	1256 ms	6364 KB	Output is correct
13	Correct	848 ms	6364 KB	Output is correct
14	Correct	1068 ms	6364 KB	Output is correct
15	Correct	1148 ms	6364 KB	Output is correct
16	Correct	692 ms	3988 KB	Output is correct
17	Correct	1120 ms	6364 KB	Output is correct
18	Correct	948 ms	6364 KB	Output is correct
19	Correct	2292 ms	6628 KB	Output is correct
20	Correct	4476 ms	3724 KB	Output is correct
21	Correct	436 ms	1216 KB	Output is correct
22	Correct	5012 ms	6232 KB	Output is correct
23	Correct	300 ms	11380 KB	Output is correct
24	Correct	1848 ms	6892 KB	Output is correct
25	Correct	3092 ms	11380 KB	Output is correct
26	Correct	2668 ms	11380 KB	Output is correct
27	Correct	2508 ms	11380 KB	Output is correct
28	Incorrect	820 ms	55864 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	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	1244 ms	6364 KB	Output is correct
13	Correct	848 ms	6364 KB	Output is correct
14	Correct	992 ms	6364 KB	Output is correct
15	Correct	1136 ms	6364 KB	Output is correct
16	Correct	708 ms	3988 KB	Output is correct
17	Correct	1088 ms	6364 KB	Output is correct
18	Correct	956 ms	6364 KB	Output is correct
19	Correct	2324 ms	6628 KB	Output is correct
20	Correct	4492 ms	3724 KB	Output is correct
21	Correct	448 ms	1216 KB	Output is correct
22	Correct	5048 ms	6232 KB	Output is correct
23	Correct	328 ms	11380 KB	Output is correct
24	Correct	1836 ms	6892 KB	Output is correct
25	Correct	3112 ms	11380 KB	Output is correct
26	Correct	2680 ms	11380 KB	Output is correct
27	Correct	2512 ms	11380 KB	Output is correct
28	Incorrect	780 ms	55864 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #7255

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