Submission #5241

#	Time	Username	Problem	Language	Result	Execution time	Memory
5241		ainta	Game (IOI13_game)	C++98	100 / 100	9400 ms	105488 KiB

game

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

int rr, cc;
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;
}

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

struct Seg_X{
	Seg_X *c1, *c2;
	Seg_Y *cy;
	long long G;
};
Seg_X *root;

void init(int R, int C) {
	root = new Seg_X();
	rr = R, cc = C;
}

void UDT_Y(Seg_Y *node, int b, int e, int y, long long K){
	int m = (b + e) >> 1;
	if (node->K){
		if (node->K == y){
			node->G = K;
			return;
		}
		if (node->K <= m)node->c1 = new Seg_Y(node->K), node->c1->G = node->G;
		else node->c2 = new Seg_Y(node->K), node->c2->G = node->G;
		node->K = 0;
	}
	if (y <= m){
		if (!node->c1) node->c1 = new Seg_Y(y);
		UDT_Y(node->c1, b, m, y, K);
	}
	else {
		if (!node->c2) node->c2 = new Seg_Y(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(Seg_Y *node, int b, int e, int y){
	if (node == NULL)return 0;
	if (node->K){
		if (node->K == y)return node->G;
		return 0;
	}
	int m = (b + e) >> 1;
	if (y <= m)return Gap(node->c1, b, m, y);
	else return Gap(node->c2, m + 1, e, y);
}

void UDT_X(Seg_X *node, int b, int e, int x, int y, long long K){
	if (!node->cy)node->cy = new Seg_Y(y);
	if (b == e){
		UDT_Y(node->cy, 1, cc, y, K);
		return;
	}
	int m = (b + e) >> 1;
	long long r = 0;
	if (!node->c1)node->c1 = new Seg_X();
	if (!node->c2)node->c2 = new Seg_X();
	if (x <= m)UDT_X(node->c1, b, m, x, y, K);
	else UDT_X(node->c2, m + 1, e, x, y, K);
	r = Gap(node->c2->cy, 1, cc, y);
	r = gcd2(Gap(node->c1->cy, 1, cc, y), r);
	UDT_Y(node->cy, 1, cc, y, r);
}

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

long long Calc2(Seg_Y *node, int b, int e, int Q, int V){
	if (!node)return 0;
	if (node->K){
		if (node->K >= Q && node->K <= V)return node->G;
		return 0;
	}
	if (b == Q && e == V)return node->G;
	int m = (b + e) >> 1;
	long long r = 0;
	if (Q <= m && node->c1)r = Calc2(node->c1, b, m, Q, min(V,m));
	if (V > m && node->c2)r = gcd2(Calc2(node->c2, m + 1, e, max(m + 1, Q), V), r);
	return r;
}
long long Calc(Seg_X *node, int b, int e, int P, int Q, int U, int V){
	if (b == P && e == U)return Calc2(node->cy, 1, cc, Q, V);
	int m = (b + e) >> 1;
	long long r = 0;
	if (P <= m && node->c1) r = Calc(node->c1, b, m, P, Q, min(U, m), V);
	if (U > m && node->c2) r = gcd2(Calc(node->c2, m + 1, e, max(P, m + 1), Q, U, V), r);
	return r;
}

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

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