답안 #7247 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7247	2014-07-28T13:04:41 Z	Rhak	게임 (IOI13_game)	C++	63 / 100	4540 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* 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(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, 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(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 *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	1204 ms	9928 KB	Output is correct
5	Correct	904 ms	9928 KB	Output is correct
6	Correct	1044 ms	10060 KB	Output is correct
7	Correct	1212 ms	10060 KB	Output is correct
8	Correct	724 ms	5968 KB	Output is correct
9	Correct	1108 ms	10060 KB	Output is correct
10	Correct	996 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	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	2148 ms	17848 KB	Output is correct
13	Correct	3912 ms	8212 KB	Output is correct
14	Correct	476 ms	1348 KB	Output is correct
15	Correct	4540 ms	10456 KB	Output is correct
16	Correct	408 ms	21016 KB	Output is correct
17	Correct	1708 ms	12304 KB	Output is correct
18	Correct	2808 ms	21016 KB	Output is correct
19	Correct	2440 ms	21016 KB	Output is correct
20	Correct	2296 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	1252 ms	9928 KB	Output is correct
13	Correct	892 ms	9928 KB	Output is correct
14	Correct	1040 ms	10060 KB	Output is correct
15	Correct	1136 ms	10060 KB	Output is correct
16	Correct	708 ms	5968 KB	Output is correct
17	Correct	1120 ms	10060 KB	Output is correct
18	Correct	956 ms	10060 KB	Output is correct
19	Correct	2204 ms	17848 KB	Output is correct
20	Correct	3896 ms	8212 KB	Output is correct
21	Correct	496 ms	1348 KB	Output is correct
22	Correct	4484 ms	10456 KB	Output is correct
23	Correct	364 ms	21016 KB	Output is correct
24	Correct	1672 ms	12304 KB	Output is correct
25	Correct	2808 ms	21016 KB	Output is correct
26	Correct	2440 ms	21016 KB	Output is correct
27	Correct	2276 ms	21016 KB	Output is correct
28	Correct	1424 ms	242248 KB	Output is correct
29	Memory limit exceeded	3632 ms	256000 KB	Memory limit exceeded
30	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	1244 ms	9928 KB	Output is correct
13	Correct	912 ms	9928 KB	Output is correct
14	Correct	1020 ms	10060 KB	Output is correct
15	Correct	1128 ms	10060 KB	Output is correct
16	Correct	700 ms	5968 KB	Output is correct
17	Correct	1108 ms	10060 KB	Output is correct
18	Correct	948 ms	10060 KB	Output is correct
19	Correct	2120 ms	17848 KB	Output is correct
20	Correct	3892 ms	8212 KB	Output is correct
21	Correct	468 ms	1348 KB	Output is correct
22	Correct	4516 ms	10456 KB	Output is correct
23	Correct	368 ms	21016 KB	Output is correct
24	Correct	1688 ms	12304 KB	Output is correct
25	Correct	2784 ms	21016 KB	Output is correct
26	Correct	2412 ms	21016 KB	Output is correct
27	Correct	2244 ms	21016 KB	Output is correct
28	Correct	1428 ms	242248 KB	Output is correct
29	Memory limit exceeded	3684 ms	256000 KB	Memory limit exceeded
30	Halted	0 ms	0 KB	-

답안 #7247

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