답안 #30608 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30608	2017-07-25T12:11:52 Z	nibnalin	게임 (IOI13_game)	C++14	80 / 100	13000 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(L), upd(R);
}

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, lli 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	1619 ms	4136 KB	Output is correct
5	Correct	686 ms	4136 KB	Output is correct
6	Correct	3293 ms	4136 KB	Output is correct
7	Correct	3756 ms	4136 KB	Output is correct
8	Correct	2549 ms	3080 KB	Output is correct
9	Correct	3836 ms	4136 KB	Output is correct
10	Correct	2849 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	2393 ms	7304 KB	Output is correct
13	Correct	8966 ms	7304 KB	Output is correct
14	Correct	859 ms	7700 KB	Output is correct
15	Correct	9513 ms	7832 KB	Output is correct
16	Correct	479 ms	7832 KB	Output is correct
17	Correct	5503 ms	4796 KB	Output is correct
18	Correct	10073 ms	7832 KB	Output is correct
19	Correct	8386 ms	7832 KB	Output is correct
20	Correct	7893 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	1759 ms	4136 KB	Output is correct
13	Correct	703 ms	4136 KB	Output is correct
14	Correct	3356 ms	4136 KB	Output is correct
15	Correct	4223 ms	4136 KB	Output is correct
16	Correct	2639 ms	3080 KB	Output is correct
17	Correct	3856 ms	4136 KB	Output is correct
18	Correct	3389 ms	4136 KB	Output is correct
19	Correct	2603 ms	7304 KB	Output is correct
20	Correct	8699 ms	7304 KB	Output is correct
21	Correct	889 ms	7700 KB	Output is correct
22	Correct	8883 ms	7832 KB	Output is correct
23	Correct	523 ms	7832 KB	Output is correct
24	Correct	5706 ms	4796 KB	Output is correct
25	Correct	10299 ms	7832 KB	Output is correct
26	Correct	8506 ms	7832 KB	Output is correct
27	Correct	7919 ms	7832 KB	Output is correct
28	Correct	2783 ms	22088 KB	Output is correct
29	Correct	3729 ms	22088 KB	Output is correct
30	Correct	10936 ms	19580 KB	Output is correct
31	Correct	8769 ms	18920 KB	Output is correct
32	Correct	1206 ms	16544 KB	Output is correct
33	Correct	2193 ms	16544 KB	Output is correct
34	Correct	799 ms	22088 KB	Output is correct
35	Correct	5803 ms	12056 KB	Output is correct
36	Correct	10369 ms	22088 KB	Output is correct
37	Correct	8506 ms	22088 KB	Output is correct
38	Correct	8436 ms	22088 KB	Output is correct
39	Correct	7473 ms	17336 KB	Output is correct
40	Correct	0 ms	2024 KB	Output is correct

Subtask #5
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	1773 ms	4136 KB	Output is correct
13	Correct	636 ms	4136 KB	Output is correct
14	Correct	3316 ms	4136 KB	Output is correct
15	Correct	3963 ms	4136 KB	Output is correct
16	Correct	2606 ms	3080 KB	Output is correct
17	Correct	3713 ms	4136 KB	Output is correct
18	Correct	2779 ms	4136 KB	Output is correct
19	Correct	2273 ms	7304 KB	Output is correct
20	Correct	8186 ms	7304 KB	Output is correct
21	Correct	883 ms	7700 KB	Output is correct
22	Correct	8866 ms	7832 KB	Output is correct
23	Correct	673 ms	7832 KB	Output is correct
24	Correct	4883 ms	4796 KB	Output is correct
25	Correct	9033 ms	7832 KB	Output is correct
26	Correct	8396 ms	7832 KB	Output is correct
27	Correct	8223 ms	7832 KB	Output is correct
28	Correct	2123 ms	22088 KB	Output is correct
29	Correct	3773 ms	22088 KB	Output is correct
30	Correct	10319 ms	19580 KB	Output is correct
31	Correct	8889 ms	18920 KB	Output is correct
32	Correct	1306 ms	16544 KB	Output is correct
33	Correct	2159 ms	16544 KB	Output is correct
34	Correct	863 ms	22088 KB	Output is correct
35	Correct	6426 ms	12056 KB	Output is correct
36	Correct	10476 ms	22088 KB	Output is correct
37	Correct	9093 ms	22088 KB	Output is correct
38	Correct	9003 ms	22088 KB	Output is correct
39	Correct	3403 ms	45320 KB	Output is correct
40	Correct	5769 ms	45320 KB	Output is correct
41	Execution timed out	13000 ms	39908 KB	Execution timed out
42	Halted	0 ms	0 KB	-

답안 #30608

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