답안 #31429 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31429	2017-08-24T06:57:42 Z	0xrgb	게임 (IOI13_game)	C++11	80 / 100	13000 ms	60840 KB

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

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	1308 KB	Output is correct
3	Correct	1308 KB	Output is correct
4	Correct	1176 KB	Output is correct
5	Correct	1176 KB	Output is correct
6	Correct	1308 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	2353 ms	3816 KB	Output is correct
5	Correct	1012 ms	3816 KB	Output is correct
6	Correct	2809 ms	3948 KB	Output is correct
7	Correct	3739 ms	3948 KB	Output is correct
8	Correct	2313 ms	2496 KB	Output is correct
9	Correct	3243 ms	3948 KB	Output is correct
10	Correct	2889 ms	3948 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	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	3353 ms	6060 KB	Output is correct
13	Correct	7813 ms	3948 KB	Output is correct
14	Correct	906 ms	1308 KB	Output is correct
15	Correct	8783 ms	4740 KB	Output is correct
16	Correct	666 ms	7380 KB	Output is correct
17	Correct	4209 ms	4476 KB	Output is correct
18	Correct	7513 ms	7380 KB	Output is correct
19	Correct	6139 ms	7380 KB	Output is correct
20	Correct	6666 ms	7380 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	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	2293 ms	3816 KB	Output is correct
13	Correct	1016 ms	3816 KB	Output is correct
14	Correct	2813 ms	3948 KB	Output is correct
15	Correct	3423 ms	3948 KB	Output is correct
16	Correct	2156 ms	2496 KB	Output is correct
17	Correct	3273 ms	3948 KB	Output is correct
18	Correct	2993 ms	3948 KB	Output is correct
19	Correct	3546 ms	6060 KB	Output is correct
20	Correct	8179 ms	3948 KB	Output is correct
21	Correct	859 ms	1308 KB	Output is correct
22	Correct	8679 ms	4740 KB	Output is correct
23	Correct	539 ms	7380 KB	Output is correct
24	Correct	5206 ms	4476 KB	Output is correct
25	Correct	8936 ms	7380 KB	Output is correct
26	Correct	7623 ms	7380 KB	Output is correct
27	Correct	7293 ms	7380 KB	Output is correct
28	Correct	2829 ms	28896 KB	Output is correct
29	Correct	5286 ms	28896 KB	Output is correct
30	Correct	10343 ms	23220 KB	Output is correct
31	Correct	9383 ms	17676 KB	Output is correct
32	Correct	1022 ms	1308 KB	Output is correct
33	Correct	1789 ms	1836 KB	Output is correct
34	Correct	1536 ms	28896 KB	Output is correct
35	Correct	5449 ms	15036 KB	Output is correct
36	Correct	11053 ms	28896 KB	Output is correct
37	Correct	8309 ms	28896 KB	Output is correct
38	Correct	8359 ms	28896 KB	Output is correct
39	Correct	6796 ms	22428 KB	Output is correct
40	Correct	0 ms	1176 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	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	2236 ms	3816 KB	Output is correct
13	Correct	1043 ms	3816 KB	Output is correct
14	Correct	2766 ms	3948 KB	Output is correct
15	Correct	3309 ms	3948 KB	Output is correct
16	Correct	2199 ms	2496 KB	Output is correct
17	Correct	3309 ms	3948 KB	Output is correct
18	Correct	2779 ms	3948 KB	Output is correct
19	Correct	3503 ms	6060 KB	Output is correct
20	Correct	7956 ms	3948 KB	Output is correct
21	Correct	809 ms	1308 KB	Output is correct
22	Correct	8566 ms	4740 KB	Output is correct
23	Correct	679 ms	7380 KB	Output is correct
24	Correct	4469 ms	4476 KB	Output is correct
25	Correct	8539 ms	7380 KB	Output is correct
26	Correct	6539 ms	7380 KB	Output is correct
27	Correct	6033 ms	7380 KB	Output is correct
28	Correct	2413 ms	28896 KB	Output is correct
29	Correct	4706 ms	28896 KB	Output is correct
30	Correct	9553 ms	23220 KB	Output is correct
31	Correct	9049 ms	17676 KB	Output is correct
32	Correct	1129 ms	1308 KB	Output is correct
33	Correct	1803 ms	1836 KB	Output is correct
34	Correct	909 ms	28896 KB	Output is correct
35	Correct	5439 ms	15036 KB	Output is correct
36	Correct	10809 ms	28896 KB	Output is correct
37	Correct	7769 ms	28896 KB	Output is correct
38	Correct	8003 ms	28896 KB	Output is correct
39	Correct	2939 ms	60840 KB	Output is correct
40	Correct	7976 ms	60840 KB	Output is correct
41	Execution timed out	13000 ms	47772 KB	Execution timed out
42	Halted	0 ms	0 KB	-

답안 #31429

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 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
0 / 20.0