Submission #390311

#	Time	Username	Problem	Language	Result	Execution time	Memory
390311		rainboy	Game (IOI13_game)	C11	100 / 100	4283 ms	39064 KiB

game

#include "game.h"

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

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

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

int zz[1 + N], ll[1 + N], rr[1 + N], jj[1 + N], u_, l_, r_; long long xx[1 + N], yy[1 + N];

int node(int j) {
	static int _ = 1;

	zz[_] = rand_();
	jj[_] = j;
	return _++;
}

void pul(int u) {
	yy[u] = gcd(xx[u], gcd(yy[ll[u]], yy[rr[u]]));
}

void split(int u, int j) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (jj[u] < j) {
		split(rr[u], j);
		rr[u] = l_, l_ = u;
	} else if (jj[u] > j) {
		split(ll[u], j);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(v);
		return v;
	}
}

int uu[1 + N], ll_[1 + N], rr_[1 + N], t_, __ = 1, r, c;

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

int update2(int u, int j, long long x) {
	split(u, j);
	if (u_ == 0)
		u_ = node(j);
	xx[u_] = yy[u_] = x;
	return merge(merge(l_, u_), r_);
}

long long get(long long u, int j) {
	while (u)
		if (jj[u] < j)
			u = rr[u];
		else if (jj[u] > j)
			u = ll[u];
		else
			return xx[u];
	return 0;
}

int update1(int t, int il, int ir, int i, int j, long long x) {
	if (t == 0)
		t = __++;
	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);
		x = gcd(get(uu[ll_[t]], j), get(uu[rr_[t]], j));
	}
	uu[t] = update2(uu[t], j, x);
	return t;
}

long long ans;

void query2(int u, int j1, int j2, int type) {
	if (u == 0)
		return;
	if (type == 0) {
		if (j2 <= jj[u])
			query2(ll[u], j1, j2, 0);
		else if (j1 > jj[u])
			query2(rr[u], j1, j2, 0);
		else {
			ans = gcd(ans, xx[u]);
			query2(ll[u], j1, j2, 1), query2(rr[u], j1, j2, -1);
		}
	} else if (type == -1) {
		if (j2 <= jj[u])
			query2(ll[u], j1, j2, -1);
		else {
			ans = gcd(gcd(ans, yy[ll[u]]), xx[u]);
			query2(rr[u], j1, j2, -1);
		}
	} else if (type == 1) {
		if (j1 > jj[u])
			query2(rr[u], j1, j2, 1);
		else {
			ans = gcd(gcd(ans, yy[rr[u]]), xx[u]);
			query2(ll[u], j1, j2, 1);
		}
	}
}

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

	if (i2 <= il || ir <= i1 || uu[t] == 0)
		return;
	if (i1 <= il && ir <= i2) {
		query2(uu[t], j1, j2, 0);
		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: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20