제출 #750967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
750967		alex_2008	게임 (IOI13_game)	C++14	37 / 100	13084 ms	35968 KiB

game

#include "game.h"
#include <vector>
typedef long long ll;
using namespace std;
vector <vector<ll>> tree;
ll a[110][110];
int H, W;
ll __gcd(ll a, ll b) {
	while (a && b) {
		(a > b) ? a %= b : b %= a;
	}
	return a + b;
}
void update1(int R, int C, ll value, int v, int tl, int tr) {
	if (tl > C || tr < C) {
		return;
	}
	if (tl == tr) {
		tree[R][v] = value;
		return;
	}
	int tm = (tl + tr) / 2;
	update1(R, C, value, 2 * v, tl, tm);
	update1(R, C, value, 2 * v + 1, tm + 1, tr);
	tree[R][v] = __gcd(tree[R][2 * v], tree[R][2 * v + 1]);
}
ll GCD(int R, int v, int tl, int tr, int l, int r) {
	if (tl >= l && tr <= r) return tree[R][v];
	if (tl > r || tr < l) return 0;
	int tm = (tl + tr) / 2;
	return __gcd(GCD(R, 2 * v, tl, tm, l, r),
		GCD(R, 2 * v + 1, tm + 1, tr, l, r));
}
void init(int R, int C) {
	H = R;
	W = C;
	tree.resize(R);
	for (int i = 0; i < R; i++) {
		tree[i].resize(4 * C);
	}
}
void update(int R, int Q, ll K) {
	if (max(H, W) <= 100) {
		a[R][Q] = K;
		return;
 	}
	update1(R, Q, K, 1, 0, W - 1);
}
ll calculate(int P, int Q, int U, int V) {
	if (max(H, W) <= 100) {
		ll u = 0;
		for (int i = P; i <= U; i++) {
			for (int j = Q; j <= V; j++) {
				u = __gcd(u, a[i][j]);
			}
		}
		return u;
	}
	ll u = 0;
	for (int i = P; i <= U; i++) {
		u = __gcd(u, GCD(i, 1, 0, W - 1, Q, V));
	}
	return u;
}

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