답안 #30620 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30620	2017-07-25T12:48:13 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, ppnode0*_l = NULL, ppnode0*_r = NULL)
	{
		key = _key, self = _self, v = _self, 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 vv)
{
	pnode0 part1 = NULL, part2 = NULL, part3 = NULL, part4 = NULL;
	split(root, part1, part2, idx);
	split(part1, part3, part4, idx-1);
	if(!part4) part4 = new ppnode0(idx, vv);
	else part4->self = part4->v = vv;
	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	1379 ms	4004 KB	Output is correct
5	Correct	686 ms	4004 KB	Output is correct
6	Correct	2353 ms	4004 KB	Output is correct
7	Correct	2743 ms	4004 KB	Output is correct
8	Correct	1876 ms	3080 KB	Output is correct
9	Correct	2736 ms	4004 KB	Output is correct
10	Correct	2323 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	2286 ms	5720 KB	Output is correct
13	Correct	7219 ms	4136 KB	Output is correct
14	Correct	769 ms	2156 KB	Output is correct
15	Correct	7513 ms	4796 KB	Output is correct
16	Correct	413 ms	6644 KB	Output is correct
17	Correct	4213 ms	4532 KB	Output is correct
18	Correct	7013 ms	6644 KB	Output is correct
19	Correct	5736 ms	6644 KB	Output is correct
20	Correct	5649 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	1383 ms	4004 KB	Output is correct
13	Correct	743 ms	4004 KB	Output is correct
14	Correct	2456 ms	4004 KB	Output is correct
15	Correct	3149 ms	4004 KB	Output is correct
16	Correct	2019 ms	3080 KB	Output is correct
17	Correct	3179 ms	4004 KB	Output is correct
18	Correct	2599 ms	4004 KB	Output is correct
19	Correct	2259 ms	5720 KB	Output is correct
20	Correct	6909 ms	4136 KB	Output is correct
21	Correct	719 ms	2156 KB	Output is correct
22	Correct	7596 ms	4796 KB	Output is correct
23	Correct	579 ms	6644 KB	Output is correct
24	Correct	3829 ms	4532 KB	Output is correct
25	Correct	8143 ms	6644 KB	Output is correct
26	Correct	7306 ms	6644 KB	Output is correct
27	Correct	5753 ms	6644 KB	Output is correct
28	Correct	2456 ms	22088 KB	Output is correct
29	Correct	3543 ms	22088 KB	Output is correct
30	Correct	9059 ms	18128 KB	Output is correct
31	Correct	8409 ms	14168 KB	Output is correct
32	Correct	1049 ms	2156 KB	Output is correct
33	Correct	1696 ms	2552 KB	Output is correct
34	Correct	743 ms	22088 KB	Output is correct
35	Correct	5109 ms	12056 KB	Output is correct
36	Correct	9283 ms	22088 KB	Output is correct
37	Correct	7223 ms	22088 KB	Output is correct
38	Correct	6773 ms	22088 KB	Output is correct
39	Correct	5763 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	1549 ms	4004 KB	Output is correct
13	Correct	629 ms	4004 KB	Output is correct
14	Correct	2486 ms	4004 KB	Output is correct
15	Correct	3276 ms	4004 KB	Output is correct
16	Correct	1959 ms	3080 KB	Output is correct
17	Correct	2793 ms	4004 KB	Output is correct
18	Correct	2003 ms	4004 KB	Output is correct
19	Correct	2069 ms	5720 KB	Output is correct
20	Correct	6726 ms	4136 KB	Output is correct
21	Correct	813 ms	2156 KB	Output is correct
22	Correct	7286 ms	4796 KB	Output is correct
23	Correct	436 ms	6644 KB	Output is correct
24	Correct	4006 ms	4532 KB	Output is correct
25	Correct	6423 ms	6644 KB	Output is correct
26	Correct	6686 ms	6644 KB	Output is correct
27	Correct	6603 ms	6644 KB	Output is correct
28	Correct	2503 ms	22088 KB	Output is correct
29	Correct	3176 ms	22088 KB	Output is correct
30	Correct	8753 ms	18128 KB	Output is correct
31	Correct	7756 ms	14168 KB	Output is correct
32	Correct	966 ms	2156 KB	Output is correct
33	Correct	1763 ms	2552 KB	Output is correct
34	Correct	956 ms	22088 KB	Output is correct
35	Correct	5319 ms	12056 KB	Output is correct
36	Correct	7919 ms	22088 KB	Output is correct
37	Correct	6923 ms	22088 KB	Output is correct
38	Correct	6996 ms	22088 KB	Output is correct
39	Correct	3086 ms	45320 KB	Output is correct
40	Correct	5476 ms	45320 KB	Output is correct
41	Execution timed out	13000 ms	36476 KB	Execution timed out
42	Halted	0 ms	0 KB	-

답안 #30620

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