oj.uz

Submission #7247

# Submission time Handle Problem Language Result Execution time Memory
7247 2014-07-28T13:04:41 Z Rhak Game (IOI13_game) C++
63 / 100
 4540 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* 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(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, 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(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 *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 1204 ms 9928 KB Output is correct
5 Correct 904 ms 9928 KB Output is correct
6 Correct 1044 ms 10060 KB Output is correct
7 Correct 1212 ms 10060 KB Output is correct
8 Correct 724 ms 5968 KB Output is correct
9 Correct 1108 ms 10060 KB Output is correct
10 Correct 996 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 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 2148 ms 17848 KB Output is correct
13 Correct 3912 ms 8212 KB Output is correct
14 Correct 476 ms 1348 KB Output is correct
15 Correct 4540 ms 10456 KB Output is correct
16 Correct 408 ms 21016 KB Output is correct
17 Correct 1708 ms 12304 KB Output is correct
18 Correct 2808 ms 21016 KB Output is correct
19 Correct 2440 ms 21016 KB Output is correct
20 Correct 2296 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 1252 ms 9928 KB Output is correct
13 Correct 892 ms 9928 KB Output is correct
14 Correct 1040 ms 10060 KB Output is correct
15 Correct 1136 ms 10060 KB Output is correct
16 Correct 708 ms 5968 KB Output is correct
17 Correct 1120 ms 10060 KB Output is correct
18 Correct 956 ms 10060 KB Output is correct
19 Correct 2204 ms 17848 KB Output is correct
20 Correct 3896 ms 8212 KB Output is correct
21 Correct 496 ms 1348 KB Output is correct
22 Correct 4484 ms 10456 KB Output is correct
23 Correct 364 ms 21016 KB Output is correct
24 Correct 1672 ms 12304 KB Output is correct
25 Correct 2808 ms 21016 KB Output is correct
26 Correct 2440 ms 21016 KB Output is correct
27 Correct 2276 ms 21016 KB Output is correct
28 Correct 1424 ms 242248 KB Output is correct
29 Memory limit exceeded 3632 ms 256000 KB Memory limit exceeded
30 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 1244 ms 9928 KB Output is correct
13 Correct 912 ms 9928 KB Output is correct
14 Correct 1020 ms 10060 KB Output is correct
15 Correct 1128 ms 10060 KB Output is correct
16 Correct 700 ms 5968 KB Output is correct
17 Correct 1108 ms 10060 KB Output is correct
18 Correct 948 ms 10060 KB Output is correct
19 Correct 2120 ms 17848 KB Output is correct
20 Correct 3892 ms 8212 KB Output is correct
21 Correct 468 ms 1348 KB Output is correct
22 Correct 4516 ms 10456 KB Output is correct
23 Correct 368 ms 21016 KB Output is correct
24 Correct 1688 ms 12304 KB Output is correct
25 Correct 2784 ms 21016 KB Output is correct
26 Correct 2412 ms 21016 KB Output is correct
27 Correct 2244 ms 21016 KB Output is correct
28 Correct 1428 ms 242248 KB Output is correct
29 Memory limit exceeded 3684 ms 256000 KB Memory limit exceeded
30 Halted 0 ms 0 KB -