oj.uz

Submission #5237

# Submission time Handle Problem Language Result Execution time Memory
5237 2014-02-21T15:18:47 Z ainta Game (IOI13_game) C++
0 / 100
 0 ms 1204 KB 
#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->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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1204 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1204 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1204 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1204 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1204 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -