oj.uz

Submission #31428

# Submission time Handle Problem Language Result Execution time Memory
31428 2017-08-24T06:30:13 Z 0xrgb Game (IOI13_game) C++14
37 / 100
 13000 ms 3948 KB 
#include <cstdio>
#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() {
		left = right = nullptr;
		rr = RAND();
		val = gg = 0;
	}
	~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();
		p2->idx = p;
		p2->val = p2->gg = 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 == 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1308 KB Output is correct
3 Correct 0 ms 1308 KB Output is correct
4 Correct 0 ms 1176 KB Output is correct
5 Correct 0 ms 1176 KB Output is correct
6 Correct 0 ms 1308 KB Output is correct
7 Correct 0 ms 1176 KB Output is correct
8 Correct 0 ms 1176 KB Output is correct
9 Correct 0 ms 1176 KB Output is correct
10 Correct 0 ms 1176 KB Output is correct
11 Correct 0 ms 1176 KB Output is correct
12 Correct 0 ms 1176 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1176 KB Output is correct
3 Correct 0 ms 1176 KB Output is correct
4 Correct 3473 ms 3816 KB Output is correct
5 Correct 1203 ms 3816 KB Output is correct
6 Correct 4223 ms 3948 KB Output is correct
7 Correct 5109 ms 3948 KB Output is correct
8 Correct 3123 ms 2496 KB Output is correct
9 Correct 4856 ms 3948 KB Output is correct
10 Correct 4075 ms 3948 KB Output is correct
11 Correct 0 ms 1176 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1308 KB Output is correct
3 Correct 0 ms 1308 KB Output is correct
4 Correct 0 ms 1176 KB Output is correct
5 Correct 0 ms 1176 KB Output is correct
6 Correct 0 ms 1308 KB Output is correct
7 Correct 0 ms 1176 KB Output is correct
8 Correct 0 ms 1176 KB Output is correct
9 Correct 0 ms 1176 KB Output is correct
10 Correct 0 ms 1176 KB Output is correct
11 Correct 0 ms 1176 KB Output is correct
12 Execution timed out 13000 ms 3684 KB Execution timed out
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1308 KB Output is correct
3 Correct 0 ms 1308 KB Output is correct
4 Correct 0 ms 1176 KB Output is correct
5 Correct 0 ms 1176 KB Output is correct
6 Correct 0 ms 1308 KB Output is correct
7 Correct 0 ms 1176 KB Output is correct
8 Correct 0 ms 1176 KB Output is correct
9 Correct 0 ms 1176 KB Output is correct
10 Correct 0 ms 1176 KB Output is correct
11 Correct 0 ms 1176 KB Output is correct
12 Correct 3199 ms 3816 KB Output is correct
13 Correct 1169 ms 3816 KB Output is correct
14 Correct 4239 ms 3948 KB Output is correct
15 Correct 5019 ms 3948 KB Output is correct
16 Correct 3326 ms 2496 KB Output is correct
17 Correct 4879 ms 3948 KB Output is correct
18 Correct 4123 ms 3948 KB Output is correct
19 Execution timed out 13000 ms 3684 KB Execution timed out
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1308 KB Output is correct
3 Correct 0 ms 1308 KB Output is correct
4 Correct 0 ms 1176 KB Output is correct
5 Correct 0 ms 1176 KB Output is correct
6 Correct 0 ms 1308 KB Output is correct
7 Correct 0 ms 1176 KB Output is correct
8 Correct 0 ms 1176 KB Output is correct
9 Correct 0 ms 1176 KB Output is correct
10 Correct 0 ms 1176 KB Output is correct
11 Correct 0 ms 1176 KB Output is correct
12 Correct 3556 ms 3816 KB Output is correct
13 Correct 1253 ms 3816 KB Output is correct
14 Correct 4433 ms 3948 KB Output is correct
15 Correct 4996 ms 3948 KB Output is correct
16 Correct 3439 ms 2496 KB Output is correct
17 Correct 4706 ms 3948 KB Output is correct
18 Correct 4389 ms 3948 KB Output is correct
19 Execution timed out 13000 ms 3684 KB Execution timed out
20 Halted 0 ms 0 KB -