Submission #4650

#	Time	Username	Problem	Language	Result	Execution time	Memory
4650		ainta	Game (IOI13_game)	C++98	0 / 100	0 ms	1204 KiB

game

#include "game.h"
#include <stdio.h>
#include <algorithm>
using namespace std;

int N, M;

struct Y_Seg{
	Y_Seg *c1, *c2;
	int b;
	long long G;
	Y_Seg(int p){ c1 = c2 = NULL, G = 0, b = p; }
};

struct X_Seg{
	X_Seg *c1, *c2;
	Y_Seg *cy;
	X_Seg(){ c1 = c2 = NULL, cy = NULL; }
};

X_Seg *root;

long long gcd2(long long X, long long Y) {
	long long tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}

void init(int R, int C) {
	N = R, M = C;
	root = new X_Seg();
}

void UDT_Y(Y_Seg *node, int b, int e, int y, long long K){
	int t, m = (b + e) >> 1;
	if (node->b){
		if (node->b == y){
			node->G = K;
			return;
		}
		else{
			t = node->b;
			node->b = 0;
			if (t <= m){
				node->c1 = new Y_Seg(t);
				node->c1->G = node->G;
			}
			else{
				node->c2 = new Y_Seg(t);
				node->c2->G = node->G;
			}
		}
	}
	if (y <= m){
		if (!node->c1)node->c1 = new Y_Seg(y);
		UDT_Y(node->c1, b, m, y, K);
	}
	else{
		if (!node->c2)node->c2 = new Y_Seg(y);
		UDT_Y(node->c2, m + 1, e, y, K);
	}
	node->G = gcd2(node->c1 ? node->c1->G : 0, node->c2 ? node->c2->G : 0);
}

long long Gap_Leaf(X_Seg *node, int y){
	if (node == NULL)return 0;
	Y_Seg *p = node->cy;
	int b = 1, e = M, m;
	while (p != NULL){
		if (p->b){
			return p->b == y ? p->G : 0;
		}
		m = (b + e) >> 1;
		if (m >= y) p = p->c1;
		else p = p->c2;
	}
	return 0;
}

void UDT_X(X_Seg *node, int b, int e, int x, int y, long long K){
	if (!node->cy)node->cy = new Y_Seg(y);
	if (b == e){
		UDT_Y(node->cy, 1, M, y, K);
		return;
	}
	int m = (b + e) >> 1;
	long long G = 0;
	if (x <= m){
		if (!node->c1)node->c1 = new X_Seg();
		UDT_X(node->c1, b, m, x, y, K);
	}
	else{
		if (!node->c2)node->c2 = new X_Seg();
		UDT_X(node->c2, m + 1, e, x, y, K);
	}
	G = gcd2(Gap_Leaf(node->c1, y), Gap_Leaf(node->c2, y));
	UDT_Y(node->cy, 1, M, y, G);
}

void update(int P, int Q, long long K) {
	UDT_X(root, 1, N, P+1, Q+1, K);
}

long long CalcY(Y_Seg *node, int b, int e, int s, int l){
	if (node->b){
		if (s <= node->b && node->b <= l) return node->G;
		return 0;
	}
	if (b == s && e == l)return node->G;
	int m = (b + e) >> 1;
	long long G = 0;
	if (m >= s && node->c1)G = CalcY(node->c1, b, m, s, min(l, m));
	if (m < l && node->c2)G = gcd2(G, CalcY(node->c2, m + 1, e, max(s, m + 1), l));
	return G;
}

long long CalcX(X_Seg *node, int b, int e, int P, int Q, int U, int V){
	int m = (b + e) >> 1;
	if (b == P && e == U){
		return CalcY(node->cy, 1, M, Q, V);
	}
	long long G = 0;
	if (m >= P){
		if (node->c1)G = CalcX(node->c1, b, m, P, Q, min(m, U), V);
	}
	if (m < U){
		if (node->c2)G = gcd2(G, CalcX(node->c2, m + 1, e, max(P, m + 1), Q, U, V));
	}
	return G;
}

long long calculate(int P, int Q, int U, int V) {
	return CalcX(root, 1, N, P+1, Q+1, U+1, V+1);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20