oj.uz

답안 #7239

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
7239 2014-07-28T12:46:31 Z Rhak 게임 (IOI13_game) C++
0 / 100
 1212 ms 14680 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
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Incorrect 0 ms 1348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 27.0

# 결과 실행 시간 메모리 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 Incorrect 1212 ms 14680 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Incorrect 0 ms 1348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Incorrect 0 ms 1348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Incorrect 0 ms 1348 KB Output isn't correct
3 Halted 0 ms 0 KB -