oj.uz

Submission #31431

# Submission time Handle Problem Language Result Execution time Memory
31431 2017-08-24T08:18:04 Z 0xrgb Game (IOI13_game) C++14
100 / 100
 12226 ms 50280 KB 
#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

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 1176 KB Output is correct
3 Correct 0 ms 1176 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 1176 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 1959 ms 3156 KB Output is correct
5 Correct 836 ms 3156 KB Output is correct
6 Correct 2423 ms 3156 KB Output is correct
7 Correct 2736 ms 3156 KB Output is correct
8 Correct 1936 ms 2232 KB Output is correct
9 Correct 2596 ms 3156 KB Output is correct
10 Correct 2429 ms 3156 KB Output is correct
11 Correct 0 ms 1176 KB Output is correct

Subtask #3
26.0 / 26.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 0 ms 1176 KB Output is correct
5 Correct 0 ms 1176 KB Output is correct
6 Correct 3 ms 1176 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 3059 ms 4872 KB Output is correct
13 Correct 6786 ms 3288 KB Output is correct
14 Correct 733 ms 1308 KB Output is correct
15 Correct 6779 ms 3948 KB Output is correct
16 Correct 553 ms 5928 KB Output is correct
17 Correct 3683 ms 3684 KB Output is correct
18 Correct 6879 ms 5928 KB Output is correct
19 Correct 5873 ms 5928 KB Output is correct
20 Correct 4983 ms 5928 KB Output is correct
21 Correct 0 ms 1176 KB Output is correct

Subtask #4
17.0 / 17.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 0 ms 1176 KB Output is correct
5 Correct 0 ms 1176 KB Output is correct
6 Correct 0 ms 1176 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 2193 ms 3156 KB Output is correct
13 Correct 766 ms 3156 KB Output is correct
14 Correct 2543 ms 3156 KB Output is correct
15 Correct 2766 ms 3156 KB Output is correct
16 Correct 1826 ms 2232 KB Output is correct
17 Correct 2516 ms 3156 KB Output is correct
18 Correct 2203 ms 3156 KB Output is correct
19 Correct 2996 ms 4872 KB Output is correct
20 Correct 6473 ms 3288 KB Output is correct
21 Correct 719 ms 1308 KB Output is correct
22 Correct 6716 ms 3948 KB Output is correct
23 Correct 583 ms 5928 KB Output is correct
24 Correct 3729 ms 3684 KB Output is correct
25 Correct 6873 ms 5928 KB Output is correct
26 Correct 5416 ms 5928 KB Output is correct
27 Correct 5406 ms 5928 KB Output is correct
28 Correct 2003 ms 24012 KB Output is correct
29 Correct 3973 ms 24012 KB Output is correct
30 Correct 8396 ms 18864 KB Output is correct
31 Correct 7683 ms 14508 KB Output is correct
32 Correct 1039 ms 1308 KB Output is correct
33 Correct 1689 ms 1704 KB Output is correct
34 Correct 826 ms 24012 KB Output is correct
35 Correct 4213 ms 12660 KB Output is correct
36 Correct 8726 ms 24012 KB Output is correct
37 Correct 6946 ms 24012 KB Output is correct
38 Correct 6816 ms 24012 KB Output is correct
39 Correct 6373 ms 18732 KB Output is correct
40 Correct 0 ms 1176 KB Output is correct

Subtask #5
20.0 / 20.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 0 ms 1176 KB Output is correct
5 Correct 0 ms 1176 KB Output is correct
6 Correct 0 ms 1176 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 2003 ms 3156 KB Output is correct
13 Correct 919 ms 3156 KB Output is correct
14 Correct 2489 ms 3156 KB Output is correct
15 Correct 2963 ms 3156 KB Output is correct
16 Correct 1956 ms 2232 KB Output is correct
17 Correct 2893 ms 3156 KB Output is correct
18 Correct 2576 ms 3156 KB Output is correct
19 Correct 2996 ms 4872 KB Output is correct
20 Correct 6499 ms 3288 KB Output is correct
21 Correct 753 ms 1308 KB Output is correct
22 Correct 7043 ms 3948 KB Output is correct
23 Correct 546 ms 5928 KB Output is correct
24 Correct 4093 ms 3684 KB Output is correct
25 Correct 7779 ms 5928 KB Output is correct
26 Correct 5973 ms 5928 KB Output is correct
27 Correct 5343 ms 5928 KB Output is correct
28 Correct 2316 ms 24012 KB Output is correct
29 Correct 4713 ms 24012 KB Output is correct
30 Correct 8476 ms 18864 KB Output is correct
31 Correct 7123 ms 14508 KB Output is correct
32 Correct 1029 ms 1308 KB Output is correct
33 Correct 1553 ms 1704 KB Output is correct
34 Correct 689 ms 24012 KB Output is correct
35 Correct 4649 ms 12660 KB Output is correct
36 Correct 8643 ms 24012 KB Output is correct
37 Correct 6379 ms 24012 KB Output is correct
38 Correct 7046 ms 24012 KB Output is correct
39 Correct 2633 ms 50280 KB Output is correct
40 Correct 6809 ms 50148 KB Output is correct
41 Correct 11709 ms 38796 KB Output is correct
42 Correct 10739 ms 29556 KB Output is correct
43 Correct 1599 ms 50148 KB Output is correct
44 Correct 1503 ms 1308 KB Output is correct
45 Correct 6159 ms 18732 KB Output is correct
46 Correct 11216 ms 50280 KB Output is correct
47 Correct 11496 ms 50280 KB Output is correct
48 Correct 12226 ms 50148 KB Output is correct
49 Correct 0 ms 1176 KB Output is correct