Submission #545988

#	Time	Username	Problem	Language	Result	Execution time	Memory
545988		sliviu	Game (IOI13_game)	C++17	100 / 100	2779 ms	77212 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 Y_NODE {
	Y_NODE() : left(NULL), right(NULL) { xtree = new nodex(1, C); }
	Y_NODE* left, * right;
	nodex* xtree;
} *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;
}
 
ll query1(Y_NODE* node, int s, int e, int p, int q, int u, int v) {
	if (node == NULL || s > u || e < p) return 0;
	if (p <= s && e <= u) return QueryX(q, v, node->xtree);
	int m = (s + e) >> 1;
	return gcd2(
		query1(node->left, s, m, p, q, u, v),
		query1(node->right, m + 1, e, p, q, u, v)
	);
}
 
void update1(Y_NODE* node, int s, int e, int p, int q, ll k) {
	int m = (s + e) >> 1;
	if (s == e) {
		UpdateX(q, k, node->xtree);
		return;
	}
	if (p <= m) {
		if (node->left == NULL) node->left = new Y_NODE();
		update1(node->left, s, m, p, q, k);
	}
	else {
		if (node->right == NULL) node->right = new Y_NODE();
		update1(node->right, m + 1, e, p, q, k);
	}
	ll v = gcd2(
		node->left ? QueryX(q, q, node->left->xtree) : 0,
		node->right ? QueryX(q, q, node->right->xtree) : 0
	);
	UpdateX(q, v, node->xtree);
}
 
void init(int r, int c) {
	R = r, C = c;
	root = new Y_NODE();
}
 
void update(int p, int q, ll k) {
	++p, ++q;
	update1(root, 1, R, p, q, k);
}
 
ll calculate(int p, int q, int u, int v) {
	++p, ++q, ++u, ++v;
	return query1(root, 1, R, p, q, u, v);
}

Compilation message (stderr)

game.cpp: In function 'void UpdateX(int, ll, nodex*)':
game.cpp:48:16: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   48 |   } 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