oj.uz

Submission #7237

# Submission time Handle Problem Language Result Execution time Memory
7237 2014-07-28T12:22:33 Z Rhak Game (IOI13_game) C++
63 / 100
 3256 ms 256000 KB 
#include "game.h"

long long gcd2(long long x, long long y){ return y==0? x: gcd2(y, x%y); }

struct _node{
	_node *left, *right;
	long long GCD;
	_node(long long GCD):GCD(GCD){ left = right = 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;
		}
		int m = (s+e) >> 1;
		long long t1 = n->left? n->left->GCD:0, t2 = n->right? n->right->GCD:0;
		if( p <= m ){
			if( !n->left ) n->left = new _node(0);
			update(n->left, s, m, p, N, l, r);
			t1 = n->left->GCD;
		}
		else{
			if( !n->right ) n->right = new _node(0);
			update(n->right, m+1, e, p, N, l, r);
			t2 = n->right->GCD;
		}
		n->GCD = gcd2(t1,t2);
	}
	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 t1 = n->left? read(n->left, s, m, p, q):0;
		long long t2 = n->right? read(n->right, m+1, e, p, q):0;
		return gcd2(t1, t2);
	}

	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 1224 KB Output is correct
2 Correct 0 ms 1224 KB Output is correct
3 Correct 0 ms 1224 KB Output is correct
4 Correct 0 ms 1224 KB Output is correct
5 Correct 0 ms 1224 KB Output is correct
6 Correct 0 ms 1224 KB Output is correct
7 Correct 0 ms 1224 KB Output is correct
8 Correct 0 ms 1224 KB Output is correct
9 Correct 0 ms 1224 KB Output is correct
10 Correct 0 ms 1224 KB Output is correct
11 Correct 0 ms 1224 KB Output is correct
12 Correct 0 ms 1224 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1224 KB Output is correct
2 Correct 0 ms 1224 KB Output is correct
3 Correct 0 ms 1224 KB Output is correct
4 Correct 904 ms 9408 KB Output is correct
5 Correct 648 ms 9408 KB Output is correct
6 Correct 804 ms 9672 KB Output is correct
7 Correct 896 ms 9672 KB Output is correct
8 Correct 580 ms 5976 KB Output is correct
9 Correct 892 ms 9672 KB Output is correct
10 Correct 768 ms 9672 KB Output is correct
11 Correct 0 ms 1224 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1224 KB Output is correct
2 Correct 0 ms 1224 KB Output is correct
3 Correct 0 ms 1224 KB Output is correct
4 Correct 0 ms 1224 KB Output is correct
5 Correct 0 ms 1224 KB Output is correct
6 Correct 0 ms 1224 KB Output is correct
7 Correct 0 ms 1224 KB Output is correct
8 Correct 0 ms 1224 KB Output is correct
9 Correct 0 ms 1224 KB Output is correct
10 Correct 0 ms 1224 KB Output is correct
11 Correct 0 ms 1224 KB Output is correct
12 Correct 1508 ms 12708 KB Output is correct
13 Correct 2772 ms 6372 KB Output is correct
14 Correct 452 ms 1356 KB Output is correct
15 Correct 3244 ms 8880 KB Output is correct
16 Correct 356 ms 18516 KB Output is correct
17 Correct 1412 ms 11124 KB Output is correct
18 Correct 2252 ms 18516 KB Output is correct
19 Correct 1996 ms 18516 KB Output is correct
20 Correct 1876 ms 18516 KB Output is correct
21 Correct 0 ms 1224 KB Output is correct

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1224 KB Output is correct
2 Correct 0 ms 1224 KB Output is correct
3 Correct 0 ms 1224 KB Output is correct
4 Correct 0 ms 1224 KB Output is correct
5 Correct 0 ms 1224 KB Output is correct
6 Correct 0 ms 1224 KB Output is correct
7 Correct 0 ms 1224 KB Output is correct
8 Correct 0 ms 1224 KB Output is correct
9 Correct 0 ms 1224 KB Output is correct
10 Correct 0 ms 1224 KB Output is correct
11 Correct 0 ms 1224 KB Output is correct
12 Correct 912 ms 9408 KB Output is correct
13 Correct 640 ms 9408 KB Output is correct
14 Correct 816 ms 9672 KB Output is correct
15 Correct 912 ms 9672 KB Output is correct
16 Correct 576 ms 5976 KB Output is correct
17 Correct 868 ms 9672 KB Output is correct
18 Correct 776 ms 9672 KB Output is correct
19 Correct 1536 ms 12708 KB Output is correct
20 Correct 2800 ms 6372 KB Output is correct
21 Correct 428 ms 1356 KB Output is correct
22 Correct 3256 ms 8880 KB Output is correct
23 Correct 360 ms 18516 KB Output is correct
24 Correct 1420 ms 11124 KB Output is correct
25 Correct 2312 ms 18516 KB Output is correct
26 Correct 2012 ms 18516 KB Output is correct
27 Correct 1864 ms 18516 KB Output is correct
28 Memory limit exceeded 1436 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1224 KB Output is correct
2 Correct 0 ms 1224 KB Output is correct
3 Correct 0 ms 1224 KB Output is correct
4 Correct 0 ms 1224 KB Output is correct
5 Correct 0 ms 1224 KB Output is correct
6 Correct 0 ms 1224 KB Output is correct
7 Correct 0 ms 1224 KB Output is correct
8 Correct 0 ms 1224 KB Output is correct
9 Correct 0 ms 1224 KB Output is correct
10 Correct 0 ms 1224 KB Output is correct
11 Correct 0 ms 1224 KB Output is correct
12 Correct 904 ms 9408 KB Output is correct
13 Correct 664 ms 9408 KB Output is correct
14 Correct 808 ms 9672 KB Output is correct
15 Correct 908 ms 9672 KB Output is correct
16 Correct 592 ms 5976 KB Output is correct
17 Correct 880 ms 9672 KB Output is correct
18 Correct 784 ms 9672 KB Output is correct
19 Correct 1500 ms 12708 KB Output is correct
20 Correct 2772 ms 6372 KB Output is correct
21 Correct 424 ms 1356 KB Output is correct
22 Correct 3220 ms 8880 KB Output is correct
23 Correct 332 ms 18516 KB Output is correct
24 Correct 1412 ms 11124 KB Output is correct
25 Correct 2280 ms 18516 KB Output is correct
26 Correct 2044 ms 18516 KB Output is correct
27 Correct 1856 ms 18516 KB Output is correct
28 Memory limit exceeded 1380 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -