Submission #1090390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090390		vjudge1	Game (IOI13_game)	C++17	63 / 100	1082 ms	138692 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 Rs, Cs;

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

void update(int P, int Q, ll K) {
	int row = P + Rs, col = Q + Cs;
	sgt[row][col] = K;
	while (col) {
		col = (col - 1) / 2;
		sgt[row][col] = gcd2(sgt[row][2 * col + 1], sgt[row][2 * col + 2]);
	}
	while (row) {
		row = (row - 1) / 2;
		col = Q + Cs;
		sgt[row][col] = gcd2(sgt[2 * row + 1][col], sgt[2 * row + 2][col]);
		while (col) {
			col = (col - 1) / 2;
			sgt[row][col] = gcd2(sgt[row][2 * col + 1], sgt[row][2 * col + 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 sgtget2(int rl, int rr, int l, int r, int node, int cl, int cr) {
	if (rr < cl || cr < rl) return 0;
	if (rl <= cl && cr <= rr) return sgtget(node, l, r, 0, 0, Cs);
	int cm = (cl + cr) / 2;
	return gcd2(sgtget2(rl, rr, l, r, 2 * node + 1, cl, cm), sgtget2(rl, rr, l, r, 2 * node + 2, cm + 1, cr));
}

ll calculate(int P, int Q, int U, int V) {
	return sgtget2(P, U, Q, V, 0, 0, Rs);
}

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