답안 #31428 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31428	2017-08-24T06:30:13 Z	0xrgb	게임 (IOI13_game)	C++14	37 / 100	13000 ms	3948 KB

game

#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

#	결과	메모리	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	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

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

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

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

답안 #31428

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0