Submission #29127

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
29127	2017-07-18T11:00:02 Z	nibnalin	Game (IOI13_game)	C++14	63 / 100	3913 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<lli, lli> 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;
}

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

lli qry0(pnode0 root, lli L, lli R, lli a, lli 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, lli L, lli R, lli a, lli b, lli v)
{
	if(!root) root = new ppnode1();
	if(L == R) return new ppnode1(upd0(root->ans, 0, sz.second, b, v), NULL, NULL);
	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));
		nw->ans = upd0(nw->ans, 0, sz.second, b, pusher);
		return nw;
	}
}

lli qry1(pnode1 root, lli L, lli R, lli a, lli b, lli c, lli 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, min(P, U), max(P, U), min(Q, V), max(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	2420 KB	Output is correct
3	Correct	2420 KB	Output is correct
4	Correct	2024 KB	Output is correct
5	Correct	2024 KB	Output is correct
6	Correct	2420 KB	Output is correct
7	Correct	2024 KB	Output is correct
8	Correct	2024 KB	Output is correct
9	Correct	2288 KB	Output is correct
10	Correct	2156 KB	Output is correct
11	Correct	2156 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	919 ms	35816 KB	Output is correct
5	Correct	526 ms	35816 KB	Output is correct
6	Correct	1079 ms	36212 KB	Output is correct
7	Correct	1326 ms	36212 KB	Output is correct
8	Correct	589 ms	19184 KB	Output is correct
9	Correct	1216 ms	36212 KB	Output is correct
10	Correct	1129 ms	36212 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	2420 KB	Output is correct
3	Correct	0 ms	2420 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	2420 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	2288 KB	Output is correct
10	Correct	0 ms	2156 KB	Output is correct
11	Correct	0 ms	2156 KB	Output is correct
12	Correct	1543 ms	54560 KB	Output is correct
13	Correct	3266 ms	48224 KB	Output is correct
14	Correct	513 ms	50600 KB	Output is correct
15	Correct	3639 ms	58256 KB	Output is correct
16	Correct	519 ms	67760 KB	Output is correct
17	Correct	2209 ms	35024 KB	Output is correct
18	Correct	3476 ms	67760 KB	Output is correct
19	Correct	3053 ms	67760 KB	Output is correct
20	Correct	2523 ms	67760 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	2420 KB	Output is correct
3	Correct	0 ms	2420 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	2420 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	2288 KB	Output is correct
10	Correct	0 ms	2156 KB	Output is correct
11	Correct	0 ms	2156 KB	Output is correct
12	Correct	1018 ms	35816 KB	Output is correct
13	Correct	586 ms	35816 KB	Output is correct
14	Correct	1103 ms	36212 KB	Output is correct
15	Correct	1239 ms	36212 KB	Output is correct
16	Correct	749 ms	19184 KB	Output is correct
17	Correct	1286 ms	36212 KB	Output is correct
18	Correct	959 ms	36212 KB	Output is correct
19	Correct	1579 ms	54560 KB	Output is correct
20	Correct	3256 ms	48224 KB	Output is correct
21	Correct	569 ms	50600 KB	Output is correct
22	Correct	3913 ms	58256 KB	Output is correct
23	Correct	483 ms	67760 KB	Output is correct
24	Correct	2096 ms	35024 KB	Output is correct
25	Correct	2863 ms	67760 KB	Output is correct
26	Correct	2529 ms	67760 KB	Output is correct
27	Correct	2433 ms	67760 KB	Output is correct
28	Memory limit exceeded	869 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	2420 KB	Output is correct
3	Correct	0 ms	2420 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	2420 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	2288 KB	Output is correct
10	Correct	0 ms	2156 KB	Output is correct
11	Correct	0 ms	2156 KB	Output is correct
12	Correct	1073 ms	35816 KB	Output is correct
13	Correct	756 ms	35816 KB	Output is correct
14	Correct	1008 ms	36212 KB	Output is correct
15	Correct	1189 ms	36212 KB	Output is correct
16	Correct	819 ms	19184 KB	Output is correct
17	Correct	1289 ms	36212 KB	Output is correct
18	Correct	1233 ms	36212 KB	Output is correct
19	Correct	1589 ms	54560 KB	Output is correct
20	Correct	3073 ms	48224 KB	Output is correct
21	Correct	649 ms	50600 KB	Output is correct
22	Correct	3569 ms	58256 KB	Output is correct
23	Correct	483 ms	67760 KB	Output is correct
24	Correct	1786 ms	35024 KB	Output is correct
25	Correct	3113 ms	67760 KB	Output is correct
26	Correct	2429 ms	67760 KB	Output is correct
27	Correct	2526 ms	67760 KB	Output is correct
28	Memory limit exceeded	836 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

Submission #29127

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