Submission #31431

#	Time	Username	Problem	Language	Result	Execution time	Memory
31431		0xrgb	Game (IOI13_game)	C++14	100 / 100	12226 ms	50280 KiB

game

#include <random>
#include "game.h"

// Global
typedef long long int ll;

static ll gcd2(ll u, ll v) {
	while (v > 0) {
		const ll tmp = u % v;
		u = v;
		v = tmp;
	}
	return u;
}

static std::mt19937 RAND(314159U);

// Treap (1d)
class Treap {
public:
	unsigned int rr;
	int idx;
	ll val, gg;
	Treap *left, *right;

	Treap(int i1, ll i2) : idx(i1), val(i2), gg(i2) {
		left = right = nullptr;
		rr = RAND();
	}
};

inline ll treap_getgg(Treap *root) {
	return (root ? root->gg : 0LL);
}

inline void treap_update(Treap *root) {
	if (root) root->gg = gcd2(root->val, gcd2(treap_getgg(root->left), treap_getgg(root->right)));
}

Treap* treap_merge(Treap *left, Treap *right) {
	if (!left) return right;
	else if (!right) return left;
	else if (left->rr > right->rr) {
		left->right = treap_merge(left->right, right);
		treap_update(left);
		return left;
	}

	right->left = treap_merge(left, right->left);
	treap_update(right);
	return right;
}

void treap_split(Treap *root, int p, Treap *&left, Treap *&right) {
	if (!root) {
		left = right = nullptr;
		return;
	} else if (p > root->idx) {
		treap_split(root->right, p, root->right, right);
		left = root;
	} else {
		treap_split(root->left, p, left, root->left);
		right = root;
	}
	treap_update(root);
}

void treap_insert(Treap *&root, int p, ll k) {
	Treap *p1, *p2, *p3;
	if (!root) {
		root = new Treap(p, k);
		return;
	}

	treap_split(root, p, p1, p2);
	treap_split(p2, p + 1, p2, p3);

	if (p2) p2->val = p2->gg = k;
	else p2 = new Treap(p, k);

	root = treap_merge(p1, treap_merge(p2, p3));
}

ll treap_query(Treap *&root, int ln, int rn) {
	Treap *p1, *p2, *p3;
	if (!root || ln > rn) return 0LL;
	else if (ln == rn) {
		for (p1 = root; p1; ) {
			if (p1->idx < ln) p1 = p1->right;
			else if (p1->idx > ln) p1 = p1->left;
			else return p1->val;
		}
		return 0LL;
	}

	treap_split(root, ln, p1, p2);
	treap_split(p2, rn + 1, p2, p3);

	const ll ans = treap_getgg(p2);
	root = treap_merge(p1, treap_merge(p2, p3));

	return ans;
}

// Segment Tree (2d)
class Segtree {
public:
	int ldx, rdx, mdx;
	Segtree *left, *right;
	Treap *bst;

	Segtree(int l1, int r1) : ldx(l1), rdx(r1) {
		mdx = (l1 + r1) / 2;
		left = right = nullptr;
		bst = nullptr;
	}
};

void segtree_insert(Segtree *root, int xx, int yy, ll p) {
	if (root->ldx == root->rdx) {
		return treap_insert(root->bst, yy, p);
	} else if (xx <= root->mdx) {
		if (!root->left) root->left = new Segtree(root->ldx, root->mdx);
		segtree_insert(root->left, xx, yy, p);
	} else {
		if (!root->right) root->right = new Segtree(root->mdx + 1, root->rdx);
		segtree_insert(root->right, xx, yy, p);
	}

	treap_insert(root->bst, yy, gcd2((root->left ? treap_query(root->left->bst, yy, yy) : 0LL), (root->right ? treap_query(root->right->bst, yy, yy) : 0LL)));
}

ll segtree_query(Segtree *root, int x1, int x2, int y1, int y2) {
	if (!root || x1 > root->rdx || x2 < root->ldx) return 0LL;
	else if (x1 <= root->ldx && root->rdx <= x2) return treap_query(root->bst, y1, y2);
	return gcd2(segtree_query(root->left, x1, x2, y1, y2), segtree_query(root->right, x1, x2, y1, y2));
}

// Starts from here
static Segtree *Idx;

void init(int R, int C) {
	Idx = new Segtree(0, R - 1);
}

void update(int P, int Q, ll K) {
	return segtree_insert(Idx, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
	return segtree_query(Idx, P, U, Q, V);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^

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