oj.uz

Submission #7257

# Submission time Handle Problem Language Result Execution time Memory
7257 2014-07-28T14:38:24 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 m[5] = {s-1, ( (long long)s*3 + e) >> 2, ( s + e) >> 1, ( s + (long long)e*3) >> 2, e};
			for(long long i = 0; i < 4; i++){
				int ml = m[i]+1;
				int mr = m[i+1];
				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 m[5] = {s-1, ( (long long)s*3 + e) >> 2, ( s + e) >> 1, ( s + (long long)e*3) >> 2, e};
			for(long long i = 0; i < 4; i++){
				int ml = m[i]+1;
				int mr = m[i+1];
				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 m[5] = {s-1, ( (long long)s*3 + e) >> 2, ( s + e) >> 1, ( s + (long long)e*3) >> 2, e};
			for(long long i = 0; i < 4; i++){
				int ml = m[i]+1;
				int mr = m[i+1];
				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 m[5] = {s-1, ( (long long)s*3 + e) >> 2, ( s + e) >> 1, ( s + (long long)e*3) >> 2, e};
			for(long long i = 0; i < 4; i++){
				int ml = m[i]+1;
				int mr = m[i+1];
				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 1324 ms 6364 KB Output is correct
5 Correct 912 ms 6364 KB Output is correct
6 Correct 1072 ms 6364 KB Output is correct
7 Correct 1156 ms 6364 KB Output is correct
8 Correct 704 ms 3988 KB Output is correct
9 Correct 1148 ms 6364 KB Output is correct
10 Correct 992 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 2516 ms 6628 KB Output is correct
13 Correct 4828 ms 3724 KB Output is correct
14 Correct 468 ms 1216 KB Output is correct
15 Correct 5472 ms 6232 KB Output is correct
16 Correct 320 ms 11380 KB Output is correct
17 Correct 1876 ms 6892 KB Output is correct
18 Correct 3192 ms 11380 KB Output is correct
19 Correct 2708 ms 11380 KB Output is correct
20 Correct 2548 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 1344 ms 6364 KB Output is correct
13 Correct 940 ms 6364 KB Output is correct
14 Correct 1040 ms 6364 KB Output is correct
15 Correct 1192 ms 6364 KB Output is correct
16 Correct 736 ms 3988 KB Output is correct
17 Correct 1124 ms 6364 KB Output is correct
18 Correct 972 ms 6364 KB Output is correct
19 Correct 2484 ms 6628 KB Output is correct
20 Correct 4812 ms 3724 KB Output is correct
21 Correct 472 ms 1216 KB Output is correct
22 Correct 5472 ms 6232 KB Output is correct
23 Correct 320 ms 11380 KB Output is correct
24 Correct 1872 ms 6892 KB Output is correct
25 Correct 3148 ms 11380 KB Output is correct
26 Correct 2708 ms 11380 KB Output is correct
27 Correct 2552 ms 11380 KB Output is correct
28 Correct 1128 ms 106420 KB Output is correct
29 Correct 3964 ms 115396 KB Output is correct
30 Correct 12496 ms 84772 KB Output is correct
31 Correct 11492 ms 64840 KB Output is correct
32 Correct 848 ms 1348 KB Output is correct
33 Correct 1228 ms 2536 KB Output is correct
34 Correct 632 ms 115396 KB Output is correct
35 Correct 2448 ms 58636 KB Output is correct
36 Correct 4328 ms 115396 KB Output is correct
37 Correct 3612 ms 115396 KB Output is correct
38 Correct 3488 ms 115396 KB Output is correct
39 Correct 3064 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 1332 ms 6364 KB Output is correct
13 Correct 912 ms 6364 KB Output is correct
14 Correct 1036 ms 6364 KB Output is correct
15 Correct 1172 ms 6364 KB Output is correct
16 Correct 712 ms 3988 KB Output is correct
17 Correct 1152 ms 6364 KB Output is correct
18 Correct 1000 ms 6364 KB Output is correct
19 Correct 2496 ms 6628 KB Output is correct
20 Correct 4816 ms 3724 KB Output is correct
21 Correct 472 ms 1216 KB Output is correct
22 Correct 5484 ms 6232 KB Output is correct
23 Correct 344 ms 11380 KB Output is correct
24 Correct 1896 ms 6892 KB Output is correct
25 Correct 3176 ms 11380 KB Output is correct
26 Correct 2680 ms 11380 KB Output is correct
27 Correct 2544 ms 11380 KB Output is correct
28 Correct 1104 ms 106420 KB Output is correct
29 Correct 3880 ms 115396 KB Output is correct
30 Correct 11964 ms 84772 KB Output is correct
31 Correct 11244 ms 64840 KB Output is correct
32 Correct 840 ms 1348 KB Output is correct
33 Correct 1216 ms 2536 KB Output is correct
34 Correct 632 ms 115396 KB Output is correct
35 Correct 2448 ms 58636 KB Output is correct
36 Correct 4324 ms 115396 KB Output is correct
37 Correct 3592 ms 115396 KB Output is correct
38 Correct 3496 ms 115396 KB Output is correct
39 Correct 1624 ms 223372 KB Output is correct
40 Correct 5656 ms 247000 KB Output is correct
41 Execution timed out 13000 ms 171232 KB Program timed out
42 Halted 0 ms 0 KB -