답안 #31431 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31431	2017-08-24T08:18:04 Z	0xrgb	게임 (IOI13_game)	C++14	100 / 100	12226 ms	50280 KB

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

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

#	결과	메모리	Grader output
1	Correct	1176 KB	Output is correct
2	Correct	1176 KB	Output is correct
3	Correct	1176 KB	Output is correct
4	Correct	1176 KB	Output is correct
5	Correct	1176 KB	Output is correct
6	Correct	1176 KB	Output is correct
7	Correct	1176 KB	Output is correct
8	Correct	1176 KB	Output is correct
9	Correct	1176 KB	Output is correct
10	Correct	1176 KB	Output is correct
11	Correct	1176 KB	Output is correct
12	Correct	1176 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #31431

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.0 / 17.0

Subtask #5 20.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
17.0 / 17.0

Subtask #5
20.0 / 20.0