Submission #4636

#	Time	Username	Problem	Language	Result	Execution time	Memory
4636		ainta	Game (IOI13_game)	C++98	0 / 100	0 ms	1340 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, e;
	long long G;
	Y_Seg(int p, int q){
		c1 = NULL, c2 = NULL, G = 0;
		b = p, e = q;
	}
};

struct X_Seg{
	X_Seg *c1, *c2;
	Y_Seg *cy;
	int b, e, k;
	X_Seg(int p, int q){
		c1 = NULL, c2 = NULL, cy = NULL;
		b = p, e = q, k = -1;
	}
};
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(0, N - 1);
}

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

void update_XY(X_Seg *node, int y){
	Y_Seg *n1 = node->c1->cy, *n2 = node->c2->cy, *cur = node->cy;
	int m;
	while (n1 || n2){
		cur->G = gcd2(n1 ? n1->G : 0, n2 ? n2->G : 0);
		if (cur->b == cur->e)break;
		m = (cur->b + cur->e) >> 1;
		if (!cur->c1)cur->c1 = new Y_Seg(cur->b, m);
		if (!cur->c2)cur->c2 = new Y_Seg(m + 1, cur->e);
		if (m >= y){
			cur = cur->c1;
			if (n1)n1 = n1->c1;
			if (n2)n2 = n2->c1;
		}
		else{
			cur = cur->c2;
			if (n1)n1 = n1->c2;
			if (n2)n2 = n2->c2;
		}
	}
}

void update_X(X_Seg *node, int x, int y, long long K){
	if (node->b == node->e){
		if (node->cy == NULL)node->cy = new Y_Seg(0, M - 1);
		update_Y(node->cy, y, K);
		return;
	}
	if (node->k == -1 && !node->c1 && !node->c2){
		node->k = x;
		if (node->cy == NULL)node->cy = new Y_Seg(0, M - 1);
		update_Y(node->cy, y, K);
		return;
	}
	if (node->k != -1){
		if (node->k == x){
			update_Y(node->cy, y, K);
			return;
		}
	}
	int m = (node->b + node->e) >> 1;

	if (!node->c1)node->c1 = new X_Seg(node->b, m);
	if (!node->c2)node->c2 = new X_Seg(m + 1, node->e);
	if (!node->cy)node->cy = new Y_Seg(0, M - 1);
	if (node->k != -1){
		if (node->k <= m) node->c1->cy = node->cy;
		else node->c2->cy = node->cy;
		node->cy = new Y_Seg(0, M - 1);
		node->k = -1;
	}
	if (m < x)update_X(node->c2, x, y, K);
	else update_X(node->c1, x, y, K);

	update_XY(node, y);
}

void update(int P, int Q, long long K) {
	update_X(root, P, Q, K);
}

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

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

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

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