oj.uz

Submission #7250

# Submission time Handle Problem Language Result Execution time Memory
7250 2014-07-28T13:41:31 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){
			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[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){
			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[4];
	_IndexTree *IT;
	node(int C){
		d[0] = d[1] = d[2] = d[3] = 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[4] = {0}, 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--;
				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){
			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, 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

# 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 1412 ms 6364 KB Output is correct
5 Correct 956 ms 6364 KB Output is correct
6 Correct 1080 ms 6364 KB Output is correct
7 Correct 1196 ms 6364 KB Output is correct
8 Correct 776 ms 3988 KB Output is correct
9 Correct 1192 ms 6364 KB Output is correct
10 Correct 1024 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 2612 ms 6628 KB Output is correct
13 Correct 4988 ms 3724 KB Output is correct
14 Correct 468 ms 1216 KB Output is correct
15 Correct 5712 ms 6232 KB Output is correct
16 Correct 312 ms 11380 KB Output is correct
17 Correct 1948 ms 6892 KB Output is correct
18 Correct 3288 ms 11380 KB Output is correct
19 Correct 2800 ms 11380 KB Output is correct
20 Correct 2600 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 1428 ms 6364 KB Output is correct
13 Correct 1000 ms 6364 KB Output is correct
14 Correct 1128 ms 6364 KB Output is correct
15 Correct 1208 ms 6364 KB Output is correct
16 Correct 732 ms 3988 KB Output is correct
17 Correct 1164 ms 6364 KB Output is correct
18 Correct 1072 ms 6364 KB Output is correct
19 Correct 2656 ms 6628 KB Output is correct
20 Correct 5012 ms 3724 KB Output is correct
21 Correct 472 ms 1216 KB Output is correct
22 Correct 5732 ms 6232 KB Output is correct
23 Correct 332 ms 11380 KB Output is correct
24 Correct 1936 ms 6892 KB Output is correct
25 Correct 3260 ms 11380 KB Output is correct
26 Correct 2812 ms 11380 KB Output is correct
27 Correct 2624 ms 11380 KB Output is correct
28 Correct 1148 ms 106420 KB Output is correct
29 Correct 4032 ms 115396 KB Output is correct
30 Correct 12652 ms 84772 KB Output is correct
31 Correct 11720 ms 64840 KB Output is correct
32 Correct 872 ms 1348 KB Output is correct
33 Correct 1240 ms 2536 KB Output is correct
34 Correct 632 ms 115396 KB Output is correct
35 Correct 2472 ms 58636 KB Output is correct
36 Correct 4400 ms 115396 KB Output is correct
37 Correct 3656 ms 115396 KB Output is correct
38 Correct 3612 ms 115396 KB Output is correct
39 Correct 3116 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 1412 ms 6364 KB Output is correct
13 Correct 960 ms 6364 KB Output is correct
14 Correct 1060 ms 6364 KB Output is correct
15 Correct 1188 ms 6364 KB Output is correct
16 Correct 744 ms 3988 KB Output is correct
17 Correct 1144 ms 6364 KB Output is correct
18 Correct 1000 ms 6364 KB Output is correct
19 Correct 2644 ms 6628 KB Output is correct
20 Correct 4964 ms 3724 KB Output is correct
21 Correct 472 ms 1216 KB Output is correct
22 Correct 5692 ms 6232 KB Output is correct
23 Correct 316 ms 11380 KB Output is correct
24 Correct 1904 ms 6892 KB Output is correct
25 Correct 3216 ms 11380 KB Output is correct
26 Correct 2748 ms 11380 KB Output is correct
27 Correct 2624 ms 11380 KB Output is correct
28 Correct 1104 ms 106420 KB Output is correct
29 Correct 4040 ms 115396 KB Output is correct
30 Correct 12532 ms 84772 KB Output is correct
31 Correct 11596 ms 64840 KB Output is correct
32 Correct 860 ms 1348 KB Output is correct
33 Correct 1268 ms 2536 KB Output is correct
34 Correct 648 ms 115396 KB Output is correct
35 Correct 2472 ms 58636 KB Output is correct
36 Correct 4500 ms 115396 KB Output is correct
37 Correct 3652 ms 115396 KB Output is correct
38 Correct 3604 ms 115396 KB Output is correct
39 Correct 1660 ms 223372 KB Output is correct
40 Correct 5872 ms 247000 KB Output is correct
41 Execution timed out 13000 ms 170572 KB Program timed out
42 Halted 0 ms 0 KB -