Submission #411624

#	Time	Username	Problem	Language	Result	Execution time	Memory
411624		Mlxa	Game (IOI13_game)	C++14	10 / 100	13086 ms	9968 KiB

game

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "game.h"

const int INF = 1e9;
const int KK = 300;

ll gcd(ll x, ll y) {
	ll tmp;
	while (x != y && y != 0) {
		tmp = x;
		x = y;
		y = tmp % y;
	}
	return x;
}

struct block {
	int xl, xr, n;
	vector<pair<pii, ll>> cut;
	vector<int> y;
	vector<ll> t;
	int id(int v) {
		return (int)(lower_bound(all(y), v) - y.begin());
	}
	block(vector<pair<pii, ll>> _cut) : cut(_cut) {
		assert(cut.size());
		xl = INF, xr = -INF;
		for (auto e : cut) {
			xl = min(xl, e.x.x);
			xr = max(xr, e.x.x);
			y.push_back(e.x.y);
		}
		n = (int)y.size();
		sort(all(y));
		t.assign(2 * n, 0);
		for (auto e : cut) {
			int v = n + id(e.x.y);
			t[v] = gcd(t[v], e.y);
		}
		for (int i = n - 1; i > 0; --i) {
			t[i] = gcd(t[i + i], t[i + i + 1]);
		}
	}
	ll query(int l, int r) {
		l = id(l), r = id(r + 1) - 1;
		// cout << "query " << l << " " << r << endl;
		// for (int i = 0; i < n; ++i) {
		// 	cout << t[i + n] << " ";
		// }
		// cout << endl;
		ll res = 0;
		for (l += n, r += n; l <= r; l /= 2, r /= 2) {
			if (l % 2 == 1) {
				res = gcd(res, t[l++]);
			}
			if (r % 2 == 0) {
				res = gcd(res, t[r--]);
			}
		}
		return res;
	}
};

map<pii, ll> updates;
vector<block> blocks;

void init(int r, int c) {
	(void)r; (void)c;
}


void update(int p, int q, ll k) {
	auto cur = mp(p, q);
	updates[cur] = k;
	blocks.clear();
	vector<pair<pii, ll>> buf;
	for (auto e : updates) {
		while (buf.size() && buf.back().x == e.x) {
			buf.pop_back();
		}
	}
	for (auto e : updates) {
		buf.push_back(e);
		if ((int)buf.size() == KK) {
			blocks.emplace_back(buf);
			buf.clear();
		}
	}
	if (buf.size()) {
		blocks.emplace_back(buf);
		buf.clear();
	}
}

ll calculate(int p, int q, int u, int v) {
	ll ans = 0;
	for (auto e : blocks) {
		if (e.xr < p || e.xl > u) {
			continue;
		}
		if (p <= e.xl && e.xr <= u) {
			ans = gcd(ans, e.query(q, v));
			continue;
		}
		for (auto i : e.cut) {
			if (p <= i.x.x && i.x.x <= u && q <= i.x.y && i.x.y <= v) {
				ans = gcd(ans, i.y);
			}
		}
	}
	return ans;
}

#ifdef LC
#include "grader.c"
#endif

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