답안 #30614 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30614	2017-07-25T12:32:45 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 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);
}

bool deltaval(pnode0& t, int k, lli val)
{
	if(!t) return 0;
	bool ret = 0;
	if(t->key == k)
	{
		t->self = val;
		ret = 1;
	}
	else if(t->key < k) ret = deltaval(t->r, k, val);
	else ret = deltaval(t->l, k, val);
	if(ret) upd(t);
	return ret;
}

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)
{
	if(deltaval(root, idx, v)) return;

	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	1453 ms	4004 KB	Output is correct
5	Correct	716 ms	4004 KB	Output is correct
6	Correct	2443 ms	4004 KB	Output is correct
7	Correct	3203 ms	4004 KB	Output is correct
8	Correct	1973 ms	3080 KB	Output is correct
9	Correct	3129 ms	4004 KB	Output is correct
10	Correct	2279 ms	4004 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	1923 ms	5720 KB	Output is correct
13	Correct	6616 ms	4136 KB	Output is correct
14	Correct	819 ms	2156 KB	Output is correct
15	Correct	7569 ms	4796 KB	Output is correct
16	Correct	523 ms	6644 KB	Output is correct
17	Correct	4746 ms	4532 KB	Output is correct
18	Correct	7063 ms	6644 KB	Output is correct
19	Correct	6816 ms	6644 KB	Output is correct
20	Correct	5963 ms	6644 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	1533 ms	4004 KB	Output is correct
13	Correct	589 ms	4004 KB	Output is correct
14	Correct	2649 ms	4004 KB	Output is correct
15	Correct	3119 ms	4004 KB	Output is correct
16	Correct	1969 ms	3080 KB	Output is correct
17	Correct	2653 ms	4004 KB	Output is correct
18	Correct	2149 ms	4004 KB	Output is correct
19	Correct	2056 ms	5720 KB	Output is correct
20	Correct	7046 ms	4136 KB	Output is correct
21	Correct	746 ms	2156 KB	Output is correct
22	Correct	7143 ms	4796 KB	Output is correct
23	Correct	386 ms	6644 KB	Output is correct
24	Correct	3709 ms	4532 KB	Output is correct
25	Correct	6406 ms	6644 KB	Output is correct
26	Correct	6333 ms	6644 KB	Output is correct
27	Correct	5889 ms	6644 KB	Output is correct
28	Correct	2709 ms	22088 KB	Output is correct
29	Correct	3799 ms	22088 KB	Output is correct
30	Correct	8689 ms	18128 KB	Output is correct
31	Correct	7716 ms	14168 KB	Output is correct
32	Correct	1002 ms	2156 KB	Output is correct
33	Correct	1656 ms	2552 KB	Output is correct
34	Correct	736 ms	22088 KB	Output is correct
35	Correct	5133 ms	12056 KB	Output is correct
36	Correct	10446 ms	22088 KB	Output is correct
37	Correct	6453 ms	22088 KB	Output is correct
38	Correct	6886 ms	22088 KB	Output is correct
39	Correct	5629 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	1559 ms	4004 KB	Output is correct
13	Correct	496 ms	4004 KB	Output is correct
14	Correct	2253 ms	4004 KB	Output is correct
15	Correct	3153 ms	4004 KB	Output is correct
16	Correct	1866 ms	3080 KB	Output is correct
17	Correct	3146 ms	4004 KB	Output is correct
18	Correct	2183 ms	4004 KB	Output is correct
19	Correct	1986 ms	5720 KB	Output is correct
20	Correct	6866 ms	4136 KB	Output is correct
21	Correct	726 ms	2156 KB	Output is correct
22	Correct	6989 ms	4796 KB	Output is correct
23	Correct	559 ms	6644 KB	Output is correct
24	Correct	4706 ms	4532 KB	Output is correct
25	Correct	6186 ms	6644 KB	Output is correct
26	Correct	5553 ms	6644 KB	Output is correct
27	Correct	5786 ms	6644 KB	Output is correct
28	Correct	2573 ms	22088 KB	Output is correct
29	Correct	3213 ms	22088 KB	Output is correct
30	Correct	8426 ms	18128 KB	Output is correct
31	Correct	7626 ms	14168 KB	Output is correct
32	Correct	969 ms	2156 KB	Output is correct
33	Correct	1643 ms	2552 KB	Output is correct
34	Correct	756 ms	22088 KB	Output is correct
35	Correct	4609 ms	12056 KB	Output is correct
36	Correct	8259 ms	22088 KB	Output is correct
37	Correct	6563 ms	22088 KB	Output is correct
38	Correct	6896 ms	22088 KB	Output is correct
39	Correct	3349 ms	45320 KB	Output is correct
40	Correct	6339 ms	45320 KB	Output is correct
41	Execution timed out	13000 ms	36476 KB	Execution timed out
42	Halted	0 ms	0 KB	-

답안 #30614

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