답안 #7251 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7251	2014-07-28T13:49:21 Z	Rhak	게임 (IOI13_game)	C++	80 / 100	11264 ms	256000 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 < 3; 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){
			for(long long 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, 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[3] = {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){
			for(long long 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 *d[3];
	_IndexTree *IT;
	node(int C){
		d[0] = d[1] = d[2] = 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;
		}
		long long t[3] = {0}, fn = 0; 
		if( e >= s+3){
			for(long long i = 0; i < 3; i++){
				int ml = (( s*(3-i) + e*i) / 3) + 1;
				int mr = ( s*(2-i) + e*(i+1)) / 3;
				if(i == 0) ml--;
				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[3] = {0};
		for(int i = 0; i < 3; 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+3){
			for(long long i = 0; i < 3; i++){
				int ml = (( s*(3-i) + e*i) / 3) + 1;
				int mr = ( s*(2-i) + e*(i+1)) / 3;
				if(i == 0) ml--;
				t = n->d[i]? read(n->d[i], ml, mr, p, q, u, v):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, 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);
}

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

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	1404 ms	6492 KB	Output is correct
5	Correct	964 ms	6492 KB	Output is correct
6	Correct	1088 ms	6624 KB	Output is correct
7	Correct	1212 ms	6624 KB	Output is correct
8	Correct	736 ms	4116 KB	Output is correct
9	Correct	1168 ms	6624 KB	Output is correct
10	Correct	1036 ms	6624 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	2492 ms	8076 KB	Output is correct
13	Correct	4528 ms	4512 KB	Output is correct
14	Correct	512 ms	1212 KB	Output is correct
15	Correct	5116 ms	6492 KB	Output is correct
16	Correct	332 ms	12300 KB	Output is correct
17	Correct	1848 ms	7416 KB	Output is correct
18	Correct	3032 ms	12168 KB	Output is correct
19	Correct	2632 ms	12300 KB	Output is correct
20	Correct	2456 ms	12168 KB	Output is correct
21	Correct	0 ms	1212 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	1404 ms	6492 KB	Output is correct
13	Correct	956 ms	6492 KB	Output is correct
14	Correct	1116 ms	6624 KB	Output is correct
15	Correct	1220 ms	6624 KB	Output is correct
16	Correct	780 ms	4116 KB	Output is correct
17	Correct	1264 ms	6624 KB	Output is correct
18	Correct	1052 ms	6624 KB	Output is correct
19	Correct	2508 ms	8076 KB	Output is correct
20	Correct	4564 ms	4512 KB	Output is correct
21	Correct	524 ms	1212 KB	Output is correct
22	Correct	5136 ms	6492 KB	Output is correct
23	Correct	360 ms	12300 KB	Output is correct
24	Correct	1836 ms	7416 KB	Output is correct
25	Correct	3020 ms	12168 KB	Output is correct
26	Correct	2616 ms	12300 KB	Output is correct
27	Correct	2476 ms	12168 KB	Output is correct
28	Correct	1240 ms	132816 KB	Output is correct
29	Correct	3784 ms	144300 KB	Output is correct
30	Correct	11252 ms	105888 KB	Output is correct
31	Correct	10572 ms	80940 KB	Output is correct
32	Correct	952 ms	1344 KB	Output is correct
33	Correct	1352 ms	2796 KB	Output is correct
34	Correct	716 ms	144300 KB	Output is correct
35	Correct	2416 ms	73152 KB	Output is correct
36	Correct	4352 ms	144300 KB	Output is correct
37	Correct	3668 ms	144300 KB	Output is correct
38	Correct	3516 ms	144300 KB	Output is correct
39	Correct	3068 ms	110904 KB	Output is correct
40	Correct	0 ms	1212 KB	Output is correct

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	1428 ms	6492 KB	Output is correct
13	Correct	960 ms	6492 KB	Output is correct
14	Correct	1104 ms	6624 KB	Output is correct
15	Correct	1220 ms	6624 KB	Output is correct
16	Correct	748 ms	4116 KB	Output is correct
17	Correct	1200 ms	6624 KB	Output is correct
18	Correct	1024 ms	6624 KB	Output is correct
19	Correct	2504 ms	8076 KB	Output is correct
20	Correct	4516 ms	4512 KB	Output is correct
21	Correct	504 ms	1212 KB	Output is correct
22	Correct	5108 ms	6492 KB	Output is correct
23	Correct	352 ms	12300 KB	Output is correct
24	Correct	1840 ms	7416 KB	Output is correct
25	Correct	3064 ms	12168 KB	Output is correct
26	Correct	2660 ms	12300 KB	Output is correct
27	Correct	2472 ms	12168 KB	Output is correct
28	Correct	1252 ms	132816 KB	Output is correct
29	Correct	3796 ms	144300 KB	Output is correct
30	Correct	11264 ms	105888 KB	Output is correct
31	Correct	10580 ms	80940 KB	Output is correct
32	Correct	948 ms	1344 KB	Output is correct
33	Correct	1340 ms	2796 KB	Output is correct
34	Correct	716 ms	144300 KB	Output is correct
35	Correct	2472 ms	73152 KB	Output is correct
36	Correct	4332 ms	144300 KB	Output is correct
37	Correct	3580 ms	144300 KB	Output is correct
38	Correct	3544 ms	144300 KB	Output is correct
39	Memory limit exceeded	1664 ms	256000 KB	Memory limit exceeded
40	Halted	0 ms	0 KB	-

답안 #7251

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