Submission #390229

#	Time	Username	Problem	Language	Result	Execution time	Memory
390229		rainboy	Game (IOI13_game)	C11	0 / 100	1 ms	336 KiB

game

#include "game.h"

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

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

int r, c;
long long dd[1 + N2]; int ll_[1 + N2], rr_[1 + N2], __ = 1;
int tt[1 + N1], ll[1 + N1], rr[1 + N1], t_, _ = 1;

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

int update2(int t, int jl, int jr, int j, long long x) {
	if (t == 0)
		t = __++;
	if (jr - jl == 1)
		dd[t] = x;
	else {
		int jm = (jl + jr) / 2;

		if (j < jm)
			ll_[t] = update2(ll_[t], jl, jm, j, x);
		else
			rr_[t] = update2(rr_[t], jm, jr, j, x);
		dd[t] = gcd(dd[ll_[t]], dd[rr_[t]]);
	}
	return t;
}

int update1(int t, int il, int ir, int i, int j, long long x) {
	if (t == 0)
		t = _++;
	tt[t] = update2(tt[t], 0, c, j, x);
	if (ir - il > 1) {
		int im = (il + ir) / 2;

		if (i < im)
			ll[t] = update1(ll[t], il, im, i, j, x);
		else
			rr[t] = update1(rr[t], im, ir, i, j, x);
	}
	return t;
}

long long ans;

void query2(int t, int jl, int jr, int j1, int j2) {
	int jm;

	if (j2 <= jl || jr <= j1 || t == 0)
		return;
	if (j1 <= jl && jr <= j2) {
		ans = gcd(ans, dd[t]);
		return;
	}
	jm = (jl + jr) / 2;
	query2(ll_[t], jl, jm, j1, j2);
	query2(rr_[t], jm, jr, j1, j2);
}

void query1(int t, int il, int ir, int i1, int i2, int j1, int j2) {
	int im;

	if (i2 <= il || ir <= i1 || tt[t] == 0)
		return;
	if (i1 <= il && ir <= i2) {
		query2(tt[t], 0, c, j1, j2);
		return;
	}
	im = (il + ir) / 2;
	query1(ll[t], il, im, i1, i2, j1, j2);
	query1(rr[t], im, ir, i1, i2, j1, j2);
}

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

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

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