Submission #545996

#	Time	Username	Problem	Language	Result	Execution time	Memory
545996		sliviu	Game (IOI13_game)	C++17	100 / 100	2680 ms	77156 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

static int R, C;

ll gcd2(ll x, ll y) {
	if (y == 0) return x;
	return gcd2(y, x % y);
}

struct nodex {
	nodex* left = 0, * right = 0;
	int l, r;
	ll val;
	nodex(int _l, int _r) :l(_l), r(_r) {}
};

struct nodey {
	nodey* left = 0, * right = 0;
	nodex* val = new nodex(1, C);;
} *root;

void UpdateX(int pos, ll val, nodex* nod) {
	int l = nod->l, r = nod->r, m = (l + r) / 2;
	if (l == r) {
		nod->val = val;
		return;
	}
	nodex*& son = pos <= m ? nod->left : nod->right;
	if (!son) {
		son = new nodex(pos, pos);
		son->val = val;
	}
	else if (son->l <= pos && pos <= son->r)
		UpdateX(pos, val, son);
	else {
		do {
			if (pos <= m)
				r = m;
			else
				l = m + 1;
			m = (l + r) / 2;
		} while (pos <= m == son->r <= m);
		nodex* nn = new nodex(l, r);
		if (son->r <= m)
			nn->left = son;
		else
			nn->right = son;
		son = nn;
		UpdateX(pos, val, son);
	}
	nod->val = gcd2(nod->left ? nod->left->val : 0, nod->right ? nod->right->val : 0);
}

ll QueryX(int posleft, int posright, nodex* node) {
	if (!node)
		return 0;
	if (posleft <= node->l && node->r <= posright)
		return node->val;
	ll ans = 0;
	int m = (node->l + node->r) / 2;
	if (posleft <= m)
		ans = gcd2(ans, QueryX(posleft, posright, node->left));
	if (posright > m)
		ans = gcd2(ans, QueryX(posleft, posright, node->right));
	return ans;
}

void UpdateY(int posy, int posx, ll val, nodey* node = root, int left = 1, int right = R) {
	if (left == right) {
		UpdateX(posx, val, node->val);
		return;
	}
	int m = (left + right) / 2;
	if (posy <= m) {
		if (!node->left)
			node->left = new nodey();
		UpdateY(posy, posx, val, node->left, left, m);
	}
	else {
		if (!node->right)
			node->right = new nodey();
		UpdateY(posy, posx, val, node->right, m + 1, right);
	}
	UpdateX(posx, gcd2(node->left ? QueryX(posx, posx, node->left->val) : 0, node->right ? QueryX(posx, posx, node->right->val) : 0), node->val);
}

ll QueryY(int poslefty, int posrighty, int posleftx, int posrightx, nodey* node = root, int left = 1, int right = R) {
	if (!node)
		return 0;
	if (poslefty <= left && right <= posrighty)
		return QueryX(posleftx, posrightx, node->val);
	ll ans = 0;
	int m = (left + right) / 2;
	if (poslefty <= m)
		ans = gcd2(ans, QueryY(poslefty, posrighty, posleftx, posrightx, node->left, left, m));
	if (posrighty > m)
		ans = gcd2(ans, QueryY(poslefty, posrighty, posleftx, posrightx, node->right, m + 1, right));
	return ans;
}

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

void update(int p, int q, ll k) {
	++p, ++q;
	UpdateY(p, q, k);
}

ll calculate(int p, int q, int u, int v) {
	++p, ++q, ++u, ++v;
	return QueryY(p, u, q, v);
}

Compilation message (stderr)

game.cpp: In function 'void UpdateX(int, ll, nodex*)':
game.cpp:46:16: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   46 |   } while (pos <= m == son->r <= m);
      |            ~~~~^~~~

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