답안 #30616 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30616	2017-07-25T12:35:15 Z	nibnalin	게임 (IOI13_game)	C++14	100 / 100	12246 ms	45320 KB

game

#include <iostream>
#include <cstdio>
#include <vector>
#include <ctime>
#include <cstdlib>
#include "game.h"
using namespace std;
 
typedef long long int lli;
 
lli gcd2(lli X, lli Y) {
	lli tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}
 
struct ppnode0 {
	int key, prior;
	lli self, v;
	ppnode0 *l, *r;
	ppnode0(int _key = 0, lli _self = 0ll, lli _v = 0ll, ppnode0*_l = NULL, ppnode0*_r = NULL)
	{
		key = _key, self = _self, v = _v, l = _l, r = _r;
		prior = rand();
	}
};
 
typedef ppnode0* pnode0;
 
inline lli getv(pnode0 t)
{
	return (t?t->v:0ll);
}
 
void upd(pnode0& t)
{
	if(t) t->v = gcd2(t->self, gcd2(getv(t->l), getv(t->r)));
}
 
void split(pnode0 t, pnode0& L, pnode0& R, int k)
{
	if(!t)
	{
		L = R = NULL;
		return;
	}
	if(t->key <= k)
	{
		split(t->r, t->r, R, k);
		L = t;
	}
	else
	{
		split(t->l, L, t->l, k);
		R = t;
	}
	upd(t);
}
 
void merge(pnode0& t, pnode0 L, pnode0 R)
{
	if(!L || !R)
	{
		t = (L?L:R);
		return;
	}
	if(L->prior > R->prior)
	{
		merge(L->r, L->r, R);
		t = L;
	}
	else
	{
		merge(R->l, L, R->l);
		t = R;
	}
	upd(t);
}
 
lli findval(pnode0& t, int k)
{
	if(!t) return 0ll;
	if(t->key == k) return t->self;
	else if(t->key < k) return findval(t->r, k);
	else return findval(t->l, k);
}
 
struct ppnode1 {
	pnode0 v;
	ppnode1 *l, *r;
	ppnode1(pnode0 _v = NULL, ppnode1* _l = NULL, ppnode1* _r = NULL)
	{
		v = _v, l = _l, r = _r;
	}
};
 
typedef ppnode1* pnode1;
 
lli qry0(pnode0& root, int a, int b)
{
	if(!root) return 0;
	pnode0 part1 = NULL, part2 = NULL, part3 = NULL, part4 = NULL;
	split(root, part1, part2, b);
	split(part1, part3, part4, a-1);
	lli res = (part4?part4->v:0);
	merge(part1, part3, part4);
	merge(root, part1, part2);
	return res;
}
 
lli qry1(pnode1 root, int L, int R, int a, int b, int c, int d)
{
	if(a > R || b < L || !root) return 0ll;
	else if(a <= L && R <= b) return qry0(root->v, c, d);
	else return gcd2(qry1(root->l, L, (L+R)/2, a, b, c, d), qry1(root->r, (L+R)/2+1, R, a, b, c, d));
}
 
void upd0(pnode0& root, int idx, lli v)
{
	pnode0 part1 = NULL, part2 = NULL, part3 = NULL, part4 = NULL;
	split(root, part1, part2, idx);
	split(part1, part3, part4, idx-1);
	part4 = new ppnode0(idx, v, v, NULL, NULL);
	merge(part1, part3, part4);
	merge(root, part1, part2);
}
 
void upd1(pnode1 root, int L, int R, int a, int b, lli v)
{
	if(L == R) upd0(root->v, b, v);
	else
	{
		if(a <= (L+R)/2)
		{
			if(!root->l) root->l = new ppnode1();
			upd1(root->l, L, (L+R)/2, a, b, v);
		}
		else
		{
			if(!root->r) root->r = new ppnode1();
			upd1(root->r, (L+R)/2+1, R, a, b, v);
		}
 
		lli p = (root->l?findval(root->l->v, b):0ll), q = (root->r?findval(root->r->v, b):0ll);
		upd0(root->v, b, gcd2(p, q));
	}
	//cout << L << " " << R << " " << root->v->v << "\n";
}
 
int r, c;
pnode1 grid;
 
void init(int _R, int _C)
{
	//cout << "init\n";
	r = _R-1;
	c = _C-1;
	srand(time(NULL));
	grid = new ppnode1();
}
 
void update(int P, int Q, long long K)
{
	//cout << "update\n";
	upd1(grid, 0, r, P, Q, K);
}
 
long long calculate(int P, int Q, int U, int V)
{
	//cout << "calculate\n";
	return qry1(grid, 0, r, 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	2024 KB	Output is correct
2	Correct	2024 KB	Output is correct
3	Correct	2024 KB	Output is correct
4	Correct	2024 KB	Output is correct
5	Correct	2024 KB	Output is correct
6	Correct	2024 KB	Output is correct
7	Correct	2024 KB	Output is correct
8	Correct	2024 KB	Output is correct
9	Correct	2024 KB	Output is correct
10	Correct	2024 KB	Output is correct
11	Correct	2024 KB	Output is correct
12	Correct	2024 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2024 KB	Output is correct
2	Correct	0 ms	2024 KB	Output is correct
3	Correct	0 ms	2024 KB	Output is correct
4	Correct	1806 ms	4136 KB	Output is correct
5	Correct	576 ms	4136 KB	Output is correct
6	Correct	2663 ms	4136 KB	Output is correct
7	Correct	2706 ms	4136 KB	Output is correct
8	Correct	1729 ms	3080 KB	Output is correct
9	Correct	2479 ms	4136 KB	Output is correct
10	Correct	2186 ms	4136 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2024 KB	Output is correct
2	Correct	0 ms	2024 KB	Output is correct
3	Correct	0 ms	2024 KB	Output is correct
4	Correct	0 ms	2024 KB	Output is correct
5	Correct	0 ms	2024 KB	Output is correct
6	Correct	0 ms	2024 KB	Output is correct
7	Correct	0 ms	2024 KB	Output is correct
8	Correct	0 ms	2024 KB	Output is correct
9	Correct	0 ms	2024 KB	Output is correct
10	Correct	0 ms	2024 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	2323 ms	7304 KB	Output is correct
13	Correct	6539 ms	7304 KB	Output is correct
14	Correct	723 ms	7700 KB	Output is correct
15	Correct	7129 ms	7832 KB	Output is correct
16	Correct	499 ms	7832 KB	Output is correct
17	Correct	3866 ms	4796 KB	Output is correct
18	Correct	6646 ms	7832 KB	Output is correct
19	Correct	5993 ms	7832 KB	Output is correct
20	Correct	5553 ms	7832 KB	Output is correct
21	Correct	0 ms	2024 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2024 KB	Output is correct
2	Correct	0 ms	2024 KB	Output is correct
3	Correct	0 ms	2024 KB	Output is correct
4	Correct	0 ms	2024 KB	Output is correct
5	Correct	0 ms	2024 KB	Output is correct
6	Correct	0 ms	2024 KB	Output is correct
7	Correct	0 ms	2024 KB	Output is correct
8	Correct	0 ms	2024 KB	Output is correct
9	Correct	0 ms	2024 KB	Output is correct
10	Correct	0 ms	2024 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	1433 ms	4136 KB	Output is correct
13	Correct	696 ms	4136 KB	Output is correct
14	Correct	2636 ms	4136 KB	Output is correct
15	Correct	3056 ms	4136 KB	Output is correct
16	Correct	1876 ms	3080 KB	Output is correct
17	Correct	3093 ms	4136 KB	Output is correct
18	Correct	1953 ms	4136 KB	Output is correct
19	Correct	2456 ms	7304 KB	Output is correct
20	Correct	7086 ms	7304 KB	Output is correct
21	Correct	756 ms	7700 KB	Output is correct
22	Correct	7549 ms	7832 KB	Output is correct
23	Correct	479 ms	7832 KB	Output is correct
24	Correct	3809 ms	4796 KB	Output is correct
25	Correct	6573 ms	7832 KB	Output is correct
26	Correct	5413 ms	7832 KB	Output is correct
27	Correct	5196 ms	7832 KB	Output is correct
28	Correct	2073 ms	22088 KB	Output is correct
29	Correct	3239 ms	22088 KB	Output is correct
30	Correct	8746 ms	19580 KB	Output is correct
31	Correct	7796 ms	18920 KB	Output is correct
32	Correct	1093 ms	16544 KB	Output is correct
33	Correct	1726 ms	16544 KB	Output is correct
34	Correct	986 ms	22088 KB	Output is correct
35	Correct	4503 ms	12056 KB	Output is correct
36	Correct	8673 ms	22088 KB	Output is correct
37	Correct	6323 ms	22088 KB	Output is correct
38	Correct	7769 ms	22088 KB	Output is correct
39	Correct	6126 ms	17336 KB	Output is correct
40	Correct	0 ms	2024 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2024 KB	Output is correct
2	Correct	0 ms	2024 KB	Output is correct
3	Correct	0 ms	2024 KB	Output is correct
4	Correct	0 ms	2024 KB	Output is correct
5	Correct	0 ms	2024 KB	Output is correct
6	Correct	0 ms	2024 KB	Output is correct
7	Correct	0 ms	2024 KB	Output is correct
8	Correct	0 ms	2024 KB	Output is correct
9	Correct	0 ms	2024 KB	Output is correct
10	Correct	0 ms	2024 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	1479 ms	4136 KB	Output is correct
13	Correct	539 ms	4136 KB	Output is correct
14	Correct	2259 ms	4136 KB	Output is correct
15	Correct	2759 ms	4136 KB	Output is correct
16	Correct	1736 ms	3080 KB	Output is correct
17	Correct	2873 ms	4136 KB	Output is correct
18	Correct	2226 ms	4136 KB	Output is correct
19	Correct	2073 ms	7304 KB	Output is correct
20	Correct	6963 ms	7304 KB	Output is correct
21	Correct	829 ms	7700 KB	Output is correct
22	Correct	7539 ms	7832 KB	Output is correct
23	Correct	593 ms	7832 KB	Output is correct
24	Correct	4949 ms	4796 KB	Output is correct
25	Correct	8229 ms	7832 KB	Output is correct
26	Correct	5896 ms	7832 KB	Output is correct
27	Correct	5719 ms	7832 KB	Output is correct
28	Correct	2319 ms	22088 KB	Output is correct
29	Correct	2976 ms	22088 KB	Output is correct
30	Correct	8716 ms	19580 KB	Output is correct
31	Correct	8399 ms	18920 KB	Output is correct
32	Correct	1126 ms	16544 KB	Output is correct
33	Correct	1983 ms	16544 KB	Output is correct
34	Correct	1016 ms	22088 KB	Output is correct
35	Correct	4859 ms	12056 KB	Output is correct
36	Correct	9276 ms	22088 KB	Output is correct
37	Correct	7139 ms	22088 KB	Output is correct
38	Correct	6666 ms	22088 KB	Output is correct
39	Correct	2953 ms	45320 KB	Output is correct
40	Correct	5659 ms	45320 KB	Output is correct
41	Correct	12246 ms	40172 KB	Output is correct
42	Correct	11759 ms	38720 KB	Output is correct
43	Correct	1949 ms	45320 KB	Output is correct
44	Correct	1593 ms	33968 KB	Output is correct
45	Correct	5719 ms	17336 KB	Output is correct
46	Correct	10843 ms	45320 KB	Output is correct
47	Correct	11596 ms	45320 KB	Output is correct
48	Correct	9816 ms	45320 KB	Output is correct
49	Correct	0 ms	2024 KB	Output is correct

답안 #30616

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