Submission #29138

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
29138	2017-07-18T11:18:53 Z	nibnalin	Game (IOI13_game)	C++14	63 / 100	3819 ms	256000 KB

game

#include <iostream>
#include <cstdio>
#include <vector>
#include "game.h"
using namespace std;

typedef long long lli;

struct ppnode0 {
	lli ans;
	ppnode0 *l, *r;
	ppnode0(lli _res = 0ll, ppnode0 *_l = NULL, ppnode0 *_r = NULL)
	{
		ans = _res, l = _l, r = _r;
	}
};

struct ppnode1 {
	ppnode0* ans;
	ppnode1 *l, *r;
	ppnode1(ppnode0* _res = new ppnode0(), ppnode1 *_l = NULL, ppnode1 *_r = NULL)
	{
		ans = _res, l = _l, r = _r;
	}
};

typedef ppnode0* pnode0;
typedef ppnode1* pnode1;

pair<int, int> sz;
pnode1 grid;

long long gcd2(long long X, long long Y) {
	long long tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}

void upd0(pnode0& root, int L, int R, int b, lli v)
{
	if(L == R) root->ans = v;
	else
	{
		if(b <= (L+R)/2)
		{
			if(!root->l) root->l = new ppnode0();
			upd0(root->l, L, (L+R)/2, b, v);
		}
		else
		{
			if(!root->r) root->r = new ppnode0();
			upd0(root->r, (L+R)/2+1, R, b, v);
		}
		root->ans = 0;
		if(root->l) root->ans = gcd2(root->ans, root->l->ans);
		if(root->r) root->ans = gcd2(root->ans, root->r->ans);
	}
}

lli qry0(pnode0 root, int L, int R, int a, int b)
{
	if(a > R || b < L || !root) return 0ll;
	else if(a <= L && R <= b) return root->ans;
	else return gcd2(qry0(root->l, L, (L+R)/2, a, b), qry0(root->r, (L+R)/2+1, R, a, b));
}

pnode1 upd1(pnode1 root, int L, int R, int a, int b, lli v)
{
	if(!root) root = new ppnode1();
	if(L == R)
	{
		pnode1 nw = new ppnode1(root->ans, NULL, NULL);
		upd0(nw->ans, 0, sz.second, b, v);
		return nw;
	}
	else
	{
		pnode1 nw = new ppnode1(root->ans, NULL, NULL);
		if(a <= (L+R)/2) nw->l = upd1(root->l, L, (L+R)/2, a, b, v), nw->r = root->r;
		else nw->r = upd1(root->r, (L+R)/2+1, R, a, b, v), nw->l = root->l;
		lli pusher = 0;
		if(nw->l) pusher = gcd2(pusher, qry0(nw->l->ans, 0, sz.second, b, b));
		if(nw->r) pusher = gcd2(pusher, qry0(nw->r->ans, 0, sz.second, b, b));
		upd0(nw->ans, 0, sz.second, b, pusher);
		return nw;
	}
}

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->ans, 0, sz.second, 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 init(int _R, int _C) {
	sz.first = _R-1, sz.second = _C-1;
	grid = NULL;
}

void update(int P, int Q, long long K) {
	//cout << "upd\n";
	grid = upd1(grid, 0, sz.first, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
	//cout << "calc\n";
	return qry1(grid, 0, sz.first, 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

#	Verdict	Memory	Grader output
1	Correct	2024 KB	Output is correct
2	Correct	2156 KB	Output is correct
3	Correct	2156 KB	Output is correct
4	Correct	2024 KB	Output is correct
5	Correct	2024 KB	Output is correct
6	Correct	2156 KB	Output is correct
7	Correct	2024 KB	Output is correct
8	Correct	2024 KB	Output is correct
9	Correct	2156 KB	Output is correct
10	Correct	2156 KB	Output is correct
11	Correct	2024 KB	Output is correct
12	Correct	2024 KB	Output is correct

Subtask #2
27.0 / 27.0

#	Verdict	Execution time	Memory	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	786 ms	11660 KB	Output is correct
5	Correct	523 ms	11660 KB	Output is correct
6	Correct	923 ms	11924 KB	Output is correct
7	Correct	866 ms	11924 KB	Output is correct
8	Correct	553 ms	7436 KB	Output is correct
9	Correct	889 ms	11924 KB	Output is correct
10	Correct	1012 ms	11924 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct

Subtask #3
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2024 KB	Output is correct
2	Correct	0 ms	2156 KB	Output is correct
3	Correct	0 ms	2156 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	2156 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	2156 KB	Output is correct
10	Correct	0 ms	2156 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	1413 ms	16940 KB	Output is correct
13	Correct	2936 ms	10604 KB	Output is correct
14	Correct	423 ms	5852 KB	Output is correct
15	Correct	3773 ms	13508 KB	Output is correct
16	Correct	436 ms	23012 KB	Output is correct
17	Correct	1416 ms	13640 KB	Output is correct
18	Correct	2603 ms	23012 KB	Output is correct
19	Correct	2126 ms	23012 KB	Output is correct
20	Correct	2053 ms	23012 KB	Output is correct
21	Correct	0 ms	2024 KB	Output is correct

Subtask #4
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2024 KB	Output is correct
2	Correct	0 ms	2156 KB	Output is correct
3	Correct	0 ms	2156 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	2156 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	2156 KB	Output is correct
10	Correct	0 ms	2156 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	846 ms	11660 KB	Output is correct
13	Correct	586 ms	11660 KB	Output is correct
14	Correct	969 ms	11924 KB	Output is correct
15	Correct	993 ms	11924 KB	Output is correct
16	Correct	689 ms	7436 KB	Output is correct
17	Correct	1099 ms	11924 KB	Output is correct
18	Correct	1063 ms	11924 KB	Output is correct
19	Correct	1373 ms	16940 KB	Output is correct
20	Correct	2969 ms	10604 KB	Output is correct
21	Correct	523 ms	5852 KB	Output is correct
22	Correct	3819 ms	13508 KB	Output is correct
23	Correct	396 ms	23012 KB	Output is correct
24	Correct	1456 ms	13640 KB	Output is correct
25	Correct	3123 ms	23012 KB	Output is correct
26	Correct	2826 ms	23012 KB	Output is correct
27	Correct	2283 ms	23012 KB	Output is correct
28	Memory limit exceeded	1786 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2024 KB	Output is correct
2	Correct	0 ms	2156 KB	Output is correct
3	Correct	0 ms	2156 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	2156 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	2156 KB	Output is correct
10	Correct	0 ms	2156 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	979 ms	11660 KB	Output is correct
13	Correct	616 ms	11660 KB	Output is correct
14	Correct	1029 ms	11924 KB	Output is correct
15	Correct	1179 ms	11924 KB	Output is correct
16	Correct	713 ms	7436 KB	Output is correct
17	Correct	1126 ms	11924 KB	Output is correct
18	Correct	949 ms	11924 KB	Output is correct
19	Correct	1339 ms	16940 KB	Output is correct
20	Correct	3356 ms	10604 KB	Output is correct
21	Correct	526 ms	5852 KB	Output is correct
22	Correct	3633 ms	13508 KB	Output is correct
23	Correct	419 ms	23012 KB	Output is correct
24	Correct	1703 ms	13640 KB	Output is correct
25	Correct	2589 ms	23012 KB	Output is correct
26	Correct	2683 ms	23012 KB	Output is correct
27	Correct	2406 ms	23012 KB	Output is correct
28	Memory limit exceeded	1786 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

Submission #29138

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 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
0 / 17.0

Subtask #5
0 / 20.0