oj.uz

Submission #7251

# Submission time Handle Problem Language Result Execution time Memory
7251 2014-07-28T13:49:21 Z Rhak Game (IOI13_game) C++
80 / 100
 11264 ms 256000 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 < 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

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

Subtask #2
27.0 / 27.0

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

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

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

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