Submission #29172

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

game

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

typedef long long lli;

struct ppnode0 {
	lli ans = 0;
	ppnode0 *l = NULL, *r = NULL;
};

struct ppnode1 {
	ppnode0* ans = NULL;
	ppnode1 *l = NULL, *r = NULL;
};

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));
}

void upd1(pnode1& root, int L, int R, int a, int b, lli v)
{
	if(L == R)
	{
		if(!root->ans) root->ans = new ppnode0();
		upd0(root->ans, 0, sz.second, 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 pusher = 0;
		if(root->l) pusher = gcd2(pusher, qry0(root->l->ans, 0, sz.second, b, b));
		if(root->r) pusher = gcd2(pusher, qry0(root->r->ans, 0, sz.second, b, b));
		if(!root->ans) root->ans = new ppnode0();
		upd0(root->ans, 0, sz.second, b, pusher);
	}
}

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 = new ppnode1();
}

void update(int P, int Q, long long K) {
	//cout << "upd\n";
	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	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

#	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	893 ms	10340 KB	Output is correct
5	Correct	553 ms	10340 KB	Output is correct
6	Correct	909 ms	10472 KB	Output is correct
7	Correct	1163 ms	10472 KB	Output is correct
8	Correct	703 ms	6776 KB	Output is correct
9	Correct	919 ms	10604 KB	Output is correct
10	Correct	1026 ms	10472 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	2024 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	1579 ms	13508 KB	Output is correct
13	Correct	3056 ms	7172 KB	Output is correct
14	Correct	503 ms	2156 KB	Output is correct
15	Correct	3756 ms	9680 KB	Output is correct
16	Correct	426 ms	19184 KB	Output is correct
17	Correct	1643 ms	11924 KB	Output is correct
18	Correct	2719 ms	19184 KB	Output is correct
19	Correct	2733 ms	19316 KB	Output is correct
20	Correct	1919 ms	19184 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	2024 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	1079 ms	10340 KB	Output is correct
13	Correct	499 ms	10340 KB	Output is correct
14	Correct	723 ms	10472 KB	Output is correct
15	Correct	1236 ms	10472 KB	Output is correct
16	Correct	673 ms	6776 KB	Output is correct
17	Correct	1106 ms	10604 KB	Output is correct
18	Correct	786 ms	10472 KB	Output is correct
19	Correct	1486 ms	13508 KB	Output is correct
20	Correct	2956 ms	7172 KB	Output is correct
21	Correct	513 ms	2156 KB	Output is correct
22	Correct	3456 ms	9680 KB	Output is correct
23	Correct	289 ms	19184 KB	Output is correct
24	Correct	1736 ms	11924 KB	Output is correct
25	Correct	3166 ms	19184 KB	Output is correct
26	Correct	2639 ms	19316 KB	Output is correct
27	Correct	2226 ms	19184 KB	Output is correct
28	Correct	1476 ms	252296 KB	Output is correct
29	Memory limit exceeded	3373 ms	256000 KB	Memory limit exceeded
30	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	2024 KB	Output is correct
11	Correct	0 ms	2024 KB	Output is correct
12	Correct	959 ms	10340 KB	Output is correct
13	Correct	576 ms	10340 KB	Output is correct
14	Correct	969 ms	10472 KB	Output is correct
15	Correct	996 ms	10472 KB	Output is correct
16	Correct	706 ms	6776 KB	Output is correct
17	Correct	1116 ms	10604 KB	Output is correct
18	Correct	913 ms	10472 KB	Output is correct
19	Correct	1589 ms	13508 KB	Output is correct
20	Correct	2849 ms	7172 KB	Output is correct
21	Correct	419 ms	2156 KB	Output is correct
22	Correct	3599 ms	9680 KB	Output is correct
23	Correct	389 ms	19184 KB	Output is correct
24	Correct	1886 ms	11924 KB	Output is correct
25	Correct	2693 ms	19184 KB	Output is correct
26	Correct	2573 ms	19316 KB	Output is correct
27	Correct	2409 ms	19184 KB	Output is correct
28	Correct	1286 ms	252296 KB	Output is correct
29	Memory limit exceeded	3086 ms	256000 KB	Memory limit exceeded
30	Halted	0 ms	0 KB	-

Submission #29172

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