oj.uz

Submission #7240

# Submission time Handle Problem Language Result Execution time Memory
7240 2014-07-28T12:49:58 Z Rhak Game (IOI13_game) C++
63 / 100
 4492 ms 134404 KB 
#include "game.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(int 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(int 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

# Verdict Execution time Memory 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 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 1224 ms 9928 KB Output is correct
5 Correct 892 ms 9928 KB Output is correct
6 Correct 1032 ms 10060 KB Output is correct
7 Correct 1128 ms 10060 KB Output is correct
8 Correct 684 ms 5968 KB Output is correct
9 Correct 1100 ms 10060 KB Output is correct
10 Correct 952 ms 10060 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 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 4 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 2052 ms 17848 KB Output is correct
13 Correct 3980 ms 8212 KB Output is correct
14 Correct 480 ms 1348 KB Output is correct
15 Correct 4492 ms 10456 KB Output is correct
16 Correct 372 ms 21016 KB Output is correct
17 Correct 1676 ms 12304 KB Output is correct
18 Correct 2744 ms 21016 KB Output is correct
19 Correct 2440 ms 21016 KB Output is correct
20 Correct 2212 ms 21016 KB Output is correct
21 Correct 0 ms 1216 KB Output is correct

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory 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 1192 ms 9928 KB Output is correct
13 Correct 880 ms 9928 KB Output is correct
14 Correct 1004 ms 10060 KB Output is correct
15 Correct 1128 ms 10060 KB Output is correct
16 Correct 704 ms 5968 KB Output is correct
17 Correct 1088 ms 10060 KB Output is correct
18 Correct 996 ms 10060 KB Output is correct
19 Correct 2136 ms 17848 KB Output is correct
20 Correct 3904 ms 8212 KB Output is correct
21 Correct 472 ms 1348 KB Output is correct
22 Correct 4484 ms 10456 KB Output is correct
23 Correct 340 ms 21016 KB Output is correct
24 Correct 1700 ms 12304 KB Output is correct
25 Correct 2796 ms 21016 KB Output is correct
26 Correct 2480 ms 21016 KB Output is correct
27 Correct 2312 ms 21016 KB Output is correct
28 Incorrect 980 ms 134404 KB Output isn't correct
29 Halted 0 ms 0 KB -

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 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 1224 ms 9928 KB Output is correct
13 Correct 904 ms 9928 KB Output is correct
14 Correct 996 ms 10060 KB Output is correct
15 Correct 1116 ms 10060 KB Output is correct
16 Correct 720 ms 5968 KB Output is correct
17 Correct 1072 ms 10060 KB Output is correct
18 Correct 948 ms 10060 KB Output is correct
19 Correct 2092 ms 17848 KB Output is correct
20 Correct 3840 ms 8212 KB Output is correct
21 Correct 468 ms 1348 KB Output is correct
22 Correct 4448 ms 10456 KB Output is correct
23 Correct 360 ms 21016 KB Output is correct
24 Correct 1664 ms 12304 KB Output is correct
25 Correct 2728 ms 21016 KB Output is correct
26 Correct 2372 ms 21016 KB Output is correct
27 Correct 2228 ms 21016 KB Output is correct
28 Incorrect 992 ms 134404 KB Output isn't correct
29 Halted 0 ms 0 KB -