Submission #390253

#	Time	Username	Problem	Language	Result	Execution time	Memory
390253		rainboy	Game (IOI13_game)	C11	10 / 100	13101 ms	6796 KiB

game

#include "game.h"

#define LG	30	/* LG = ceil(log2(10^9)) */
#define NU	22000
#define N	(NU * (LG + 1))

long long gcd(long long a, long long b) {
	return b == 0 ? a : gcd(b, a % b);
}

int r, c;
long long xx[1 + N]; int ul[1 + N], ur[1 + N], dl[1 + N], dr[1 + N], t_, _ = 1;

void init(int R, int C) {
	r = R, c = C;
}

int update_(int t, int il, int ir, int jl, int jr, int i, int j, long long x) {
	if (t == 0)
		t = _++;
	if (ir - il == 1 && jr - jl == 1)
		xx[t] = x;
	else {
		int im = (il + ir) / 2, jm = (jl + jr) / 2;

		if (i < im && j < jm)
			ul[t] = update_(ul[t], il, im, jl, jm, i, j, x);
		else if (i < im && j >= jm)
			ur[t] = update_(ur[t], il, im, jm, jr, i, j, x);
		else if (i >= im && j < jm)
			dl[t] = update_(dl[t], im, ir, jl, jm, i, j, x);
		else
			dr[t] = update_(dr[t], im, ir, jm, jr, i, j, x);
		xx[t] = gcd(gcd(gcd(xx[ul[t]], xx[ur[t]]), xx[dl[t]]), xx[dr[t]]);
	}
	return t;
}

long long ans;

void query_(int t, int il, int ir, int jl, int jr, int i1, int i2, int j1, int j2) {
	int im, jm;

	if (i2 <= il || ir <= i1 || j2 <= jl || jr <= j1)
		return;
	if (i1 <= il && ir <= i2 && j1 <= jl && jr <= j2) {
		ans = gcd(ans, xx[t]);
		return;
	}
	im = (il + ir) / 2, jm = (jl + jr) / 2;
	query_(ul[t], il, im, jl, jm, i1, i2, j1, j2);
	query_(ur[t], il, im, jm, jr, i1, i2, j1, j2);
	query_(dl[t], im, ir, jl, jm, i1, i2, j1, j2);
	query_(dr[t], im, ir, jm, jr, i1, i2, j1, j2);
}

void update(int i, int j, long long x) {
	t_ = update_(t_, 0, r, 0, c, i, j, x);
}

long long calculate(int i1, int j1, int i2, int j2) {
	i2++, j2++;
	ans = 0, query_(t_, 0, r, 0, c, i1, i2, j1, j2);
	return ans;
}

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