Submission #1090380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090380		vjudge1	Game (IOI13_game)	C++17	37 / 100	13102 ms	29276 KiB

game

#include "game.h"
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;

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

vector <vector <ll>> sgt;
int Cs;

void init(int R, int C) {
	Cs = 1 << (int(ceil(log2(C))));
	Cs--;
	sgt.assign(R, vector<ll>(2 * Cs + 1, 0));
}

void update(int P, int Q, ll K) {
	int node = Q + Cs;
	sgt[P][node] = K;
	while (node) {
		node = (node - 1) / 2;
		sgt[P][node] = gcd2(sgt[P][2 * node + 1], sgt[P][2 * node + 2]);
	}
}

ll sgtget(int row, int l, int r, int node, int cl, int cr) {
	if (r < cl || cr < l) return 0;
	if (l <= cl && cr <= r) return sgt[row][node];
	int cm = (cl + cr) / 2;
	return gcd2(sgtget(row, l, r, 2 * node + 1, cl, cm), sgtget(row, l, r, 2 * node + 2, cm + 1, cr));
}

ll calculate(int P, int Q, int U, int V) {
	ll r = 0;
	for (int i = P; i <= U; i++) {
		r = gcd2(r, sgtget(i, Q, V, 0, 0, Cs));
	}
	return r;
}

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