Submission #31429

#	Time	Username	Problem	Language	Result	Execution time	Memory
31429		0xrgb	Game (IOI13_game)	C++11	80 / 100	13000 ms	60840 KiB

game

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

// global
typedef long long int ll;

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

static std::mt19937 RAND(314159);

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

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

	void recalc() {
		this->gg = gcd2(gcd2((left ? left->gg : 0LL), (right ? right->gg : 0LL)), this->val);
	}
};

static 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;
	}
	root->recalc();
}

static 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);
		left->recalc();
		return left;
	}
	else {
		right->left = treap_merge(left, right->left);
		right->recalc();
		return right;
	}
}

static void treap_insert(Treap *&root, int p, ll k) {
	Treap *p1, *p2, *p3;
	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(treap_merge(p1, p2), p3);
}

static ll treap_query(Treap *&root, int ln, int rn) {
	Treap *p1, *p2, *p3;
	if (!root) return 0LL;
	else if (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 = (p2 ? p2->gg : 0LL);
	root = treap_merge(treap_merge(p1, p2), p3);

	return ans;
}

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

	Segtree(int l1, int r1) : ldx(l1), rdx(r1) {
		left = right = nullptr;
		bst = nullptr;
	}
	~Segtree() {
		delete left;
		delete right;
		delete bst;
	}
};

static void segtree_insert(Segtree *root, int xx, int yy, ll p) {
	const int mdx = (root->ldx + root->rdx) / 2;

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

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

static ll segtree_query(Segtree *root, int x1, int x2, int y1, int y2) {
	if (x1 < root->ldx) x1 = root->ldx;
	if (x2 > root->rdx) x2 = root->rdx;

	const int mdx = (root->ldx + root->rdx) / 2;

	if (x1 > x2) return 0LL;
	else if (root->ldx == x1 && x2 == root->rdx) return treap_query(root->bst, y1, y2);
	else if (x2 <= mdx) return (root->left ? segtree_query(root->left, x1, x2, y1, y2) : 0LL);
	else if (x1 > mdx) return (root->right ? segtree_query(root->right, x1, x2, y1, y2) : 0LL);

	return gcd2((root->left ? segtree_query(root->left, x1, mdx, y1, y2) : 0LL), (root->right ? segtree_query(root->right, mdx + 1, x2, y1, y2) : 0LL));
}

// 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: 0 / 20