답안 #30619 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30619	2017-07-25T12:47:16 Z	nibnalin	게임 (IOI13_game)	C++14	100 / 100	12633 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->key = idx, 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	1496 ms	4004 KB	Output is correct
5	Correct	646 ms	4004 KB	Output is correct
6	Correct	2499 ms	4004 KB	Output is correct
7	Correct	2603 ms	4004 KB	Output is correct
8	Correct	2009 ms	3080 KB	Output is correct
9	Correct	2446 ms	4004 KB	Output is correct
10	Correct	1959 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	1843 ms	5720 KB	Output is correct
13	Correct	6826 ms	4136 KB	Output is correct
14	Correct	879 ms	2156 KB	Output is correct
15	Correct	7379 ms	4796 KB	Output is correct
16	Correct	443 ms	6644 KB	Output is correct
17	Correct	4649 ms	4532 KB	Output is correct
18	Correct	7913 ms	6644 KB	Output is correct
19	Correct	6519 ms	6644 KB	Output is correct
20	Correct	5899 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	1333 ms	4004 KB	Output is correct
13	Correct	563 ms	4004 KB	Output is correct
14	Correct	2266 ms	4004 KB	Output is correct
15	Correct	2853 ms	4004 KB	Output is correct
16	Correct	1873 ms	3080 KB	Output is correct
17	Correct	3199 ms	4004 KB	Output is correct
18	Correct	2523 ms	4004 KB	Output is correct
19	Correct	2079 ms	5720 KB	Output is correct
20	Correct	6933 ms	4136 KB	Output is correct
21	Correct	749 ms	2156 KB	Output is correct
22	Correct	7559 ms	4796 KB	Output is correct
23	Correct	426 ms	6644 KB	Output is correct
24	Correct	4246 ms	4532 KB	Output is correct
25	Correct	7363 ms	6644 KB	Output is correct
26	Correct	5726 ms	6644 KB	Output is correct
27	Correct	5873 ms	6644 KB	Output is correct
28	Correct	2103 ms	22088 KB	Output is correct
29	Correct	3703 ms	22088 KB	Output is correct
30	Correct	9456 ms	18128 KB	Output is correct
31	Correct	7796 ms	14168 KB	Output is correct
32	Correct	1099 ms	2156 KB	Output is correct
33	Correct	1959 ms	2552 KB	Output is correct
34	Correct	1133 ms	22088 KB	Output is correct
35	Correct	5156 ms	12056 KB	Output is correct
36	Correct	10243 ms	22088 KB	Output is correct
37	Correct	8313 ms	22088 KB	Output is correct
38	Correct	6866 ms	22088 KB	Output is correct
39	Correct	5986 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	1413 ms	4004 KB	Output is correct
13	Correct	683 ms	4004 KB	Output is correct
14	Correct	2793 ms	4004 KB	Output is correct
15	Correct	3476 ms	4004 KB	Output is correct
16	Correct	1969 ms	3080 KB	Output is correct
17	Correct	3206 ms	4004 KB	Output is correct
18	Correct	2196 ms	4004 KB	Output is correct
19	Correct	2179 ms	5720 KB	Output is correct
20	Correct	7246 ms	4136 KB	Output is correct
21	Correct	889 ms	2156 KB	Output is correct
22	Correct	7549 ms	4796 KB	Output is correct
23	Correct	546 ms	6644 KB	Output is correct
24	Correct	3973 ms	4532 KB	Output is correct
25	Correct	6913 ms	6644 KB	Output is correct
26	Correct	5686 ms	6644 KB	Output is correct
27	Correct	5796 ms	6644 KB	Output is correct
28	Correct	2853 ms	22088 KB	Output is correct
29	Correct	3716 ms	22088 KB	Output is correct
30	Correct	8776 ms	18128 KB	Output is correct
31	Correct	8069 ms	14168 KB	Output is correct
32	Correct	959 ms	2156 KB	Output is correct
33	Correct	1629 ms	2552 KB	Output is correct
34	Correct	783 ms	22088 KB	Output is correct
35	Correct	4633 ms	12056 KB	Output is correct
36	Correct	8686 ms	22088 KB	Output is correct
37	Correct	8183 ms	22088 KB	Output is correct
38	Correct	7126 ms	22088 KB	Output is correct
39	Correct	3353 ms	45320 KB	Output is correct
40	Correct	5366 ms	45320 KB	Output is correct
41	Correct	12633 ms	36476 KB	Output is correct
42	Correct	11689 ms	27896 KB	Output is correct
43	Correct	1409 ms	45320 KB	Output is correct
44	Correct	1366 ms	2156 KB	Output is correct
45	Correct	6136 ms	17336 KB	Output is correct
46	Correct	11616 ms	45320 KB	Output is correct
47	Correct	12119 ms	45320 KB	Output is correct
48	Correct	10933 ms	45320 KB	Output is correct
49	Correct	0 ms	2024 KB	Output is correct

답안 #30619

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