Submission #750986

#	Time	Username	Problem	Language	Result	Execution time	Memory
750986		alex_2008	Game (IOI13_game)	C++14	10 / 100	13062 ms	12360 KiB

game

#include "game.h"
#include <vector>
typedef long long ll;
using namespace std;
ll TTree[40000000];
int H, W;
ll __gcd(ll a, ll b) {
	while (a && b) {
		(a > b) ? a %= b : b %= a;
	}
	return a + b;
}
ll GCDOFLIST(vector<ll> u) {
	ll k = 0;
	for (int i = 0; i < (int)u.size(); i++) {
		k = __gcd(u[i], k);
	}
	return k;
}
void Update_(ll v, int x1, int y1, int x2, int y2, int R, int C, ll val) {
	if (x1 > x2) return;
	if (y1 > y2) return;
	bool ch = false;
	if (x1 <= R && R <= x2 && y1 <= C && C <= y2) ch = true;
	if (!ch) return;
	if (x1 == x2 && y1 == y2) {
		TTree[v] = val;
		return;
	}
	int mx = (x1 + x2) / 2;
	int my = (y1 + y2) / 2;
	Update_(4 * v, x1, y1, mx, my, R, C, val);
	Update_(4 * v + 1, x1, my + 1, mx, y2, R, C, val);
	Update_(4 * v + 2, mx + 1, y1, x2, my, R, C, val);
	Update_(4 * v + 3, mx + 1, my + 1, x2, y2, R, C, val);
	TTree[v] = 0;
	TTree[v] = __gcd(TTree[v], TTree[4 * v]);
	TTree[v] = __gcd(TTree[v], TTree[4 * v + 1]);
	TTree[v] = __gcd(TTree[v], TTree[4 * v + 2]);
	TTree[v] = __gcd(TTree[v], TTree[4 * v + 3]);
}
ll GCCCD(ll v, int x1, int y1, int x2, int y2, int xx1, int yy1, int xx2, int yy2) {
	if (x1 > x2) return 0;
	if (y1 > y2) return 0;
	if (x1 >= xx1 && y1 >= yy1 && x2 <= xx2 && y2 <= yy2) {
		return TTree[v];
	}
	bool ch = true;
	if (xx1 > x2) ch = false;
	if (xx2 < x1) ch = false;
	if (yy1 > y2) ch = false;
	if (yy2 < y1) ch = false;
	if (!ch) return 0;
	int mx = (x1 + x2) / 2;
	int my = (y1 + y2) / 2;
	return GCDOFLIST({ GCCCD(4 * v, x1, y1, mx, my, xx1, yy1, xx2, yy2),
	GCCCD(4 * v + 1, x1, my + 1, mx, y2, xx1, yy1, xx2, yy2),
	GCCCD(4 * v + 2, mx + 1, y1, x2, my, xx1, yy1, xx2, yy2),
	GCCCD(4 * v + 3, mx + 1, my + 1, x2, y2, xx1, yy1, xx2, yy2) });
}
void init(int R, int C) {
	H = 2048;
	W = 2048;
}
void update(int R, int Q, ll K) {
	Update_(1, 0, 0, H - 1, W - 1, R, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
	return GCCCD(1, 0, 0, H - 1, W - 1, P, Q, U, V);
}

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