oj.uz

Submission #7256

# Submission time Handle Problem Language Result Execution time Memory
7256 2014-07-28T14:28:06 Z Rhak Game (IOI13_game) C++
80 / 100
 13000 ms 247000 KB 
#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

# Verdict Execution time Memory 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 0 ms 1216 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -