Submission #349058

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
349058	2021-01-16T13:48:07 Z	VodkaInTheJar	Game (IOI13_game)	C++14	80 / 100	5378 ms	256000 KB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

long long gcd(long long a, long long b)
{
	while (b)
	{
		long long r = a % b;
		a = b;
		b = r; 
	}
	
	return a;
}

struct node
{
	long long val; 
	int left, right; 
	
	node() {val = 0, left = right = -1;}
};

struct segment_tree
{
	vector <node> tr;
	int left, right; 
	
	segment_tree() {tr.push_back(node()), left = right = -1;}
};

vector <segment_tree> tr; 

int r, c; 
void init(int _r, int _c)
{
	tr.push_back(segment_tree());
	r = _r;
	c = _c; 
}

void merge(int idxx, int idxy)
{
	tr[idxx].tr[idxy].val = 0;
	
	if (tr[idxx].tr[idxy].left != -1)
	tr[idxx].tr[idxy].val = gcd(tr[idxx].tr[idxy].val, tr[idxx].tr[tr[idxx].tr[idxy].left].val);
	
	if (tr[idxx].tr[idxy].right != -1)
	tr[idxx].tr[idxy].val = gcd(tr[idxx].tr[idxy].val, tr[idxx].tr[tr[idxx].tr[idxy].right].val);
}

long long small_get(int idxx, int idxy, int l, int r, int ll, int rr)
{
	if (idxy == -1 || l > rr || r < ll)
	return 0;
	
	if (l >= ll && r <= rr)
	return tr[idxx].tr[idxy].val;
	
	int mid = (l + r) / 2;
	return gcd(small_get(idxx, tr[idxx].tr[idxy].left, l, mid, ll, rr), small_get(idxx, tr[idxx].tr[idxy].right, mid + 1, r, ll, rr));
}

void small_update(int idxx, int idxy, int lx, int rx, int ly, int ry, int pos, long long val)
{
	if (ly == ry)
	{
		if (lx == rx)
		tr[idxx].tr[idxy].val = val;
		
		else 
		{
			tr[idxx].tr[idxy].val = 0; 
			if (tr[idxx].left != -1)
			tr[idxx].tr[idxy].val = gcd(tr[idxx].tr[idxy].val, small_get(tr[idxx].left, 0, 0, c-1, ly, ry));
			
			if (tr[idxx].right != -1)
			tr[idxx].tr[idxy].val = gcd(tr[idxx].tr[idxy].val, small_get(tr[idxx].right, 0, 0, c-1, ly, ry));
		}
		
		return;
	}
	
	int mid = (ly + ry) / 2;
	if (pos <= mid)
	{
		if (tr[idxx].tr[idxy].left == -1)
		{
			tr[idxx].tr.push_back(node());
			tr[idxx].tr[idxy].left = (int)tr[idxx].tr.size() - 1;
		}
		
		small_update(idxx, tr[idxx].tr[idxy].left, lx, rx, ly, mid, pos, val);
	}
	
	else 
	{
		if (tr[idxx].tr[idxy].right == -1)
		{
			tr[idxx].tr.push_back(node());
			tr[idxx].tr[idxy].right = (int)tr[idxx].tr.size() - 1; 
		}
		
		small_update(idxx, tr[idxx].tr[idxy].right, lx, rx, mid + 1, ry, pos, val);
	}
	
	merge(idxx, idxy);
}

void big_update(int idxx, int l, int r, int x, int y, long long val)
{
	if (l == r)
	{
		small_update(idxx, 0, l, r, 0, c-1, y, val);
		return;
	}
	
	int mid = (l + r) / 2;
	if (x <= mid)
	{
		if (tr[idxx].left == -1)
		{
			tr.push_back(segment_tree());
			tr[idxx].left = (int)tr.size() - 1;
		}
		
		big_update(tr[idxx].left, l, mid, x, y, val);
	}
	
	else 
	{
		if (tr[idxx].right == -1)
		{
			tr.push_back(segment_tree());
			tr[idxx].right = (int)tr.size() - 1; 
		}
		
		big_update(tr[idxx].right, mid + 1, r, x, y, val);
	}
	
	small_update(idxx, 0, l, r, 0, c-1, y, val);
}

long long big_get(int idxx, int l, int r, int lx, int rx, int ly, int ry)
{
	if (idxx == -1 || l > rx || r < lx)
	return 0;
	
	if (l >= lx && r <= rx)
	return small_get(idxx, 0, 0, c-1, ly, ry);
	
	int mid = (l + r) / 2; 
	return gcd(big_get(tr[idxx].left, l, mid, lx, rx, ly, ry), big_get(tr[idxx].right, mid + 1, r, lx, rx, ly, ry));
}

void update(int p, int q, long long k)
{
	big_update(0, 0, r, p, q, k);
}

long long calculate(int p, int q, int u, int v)
{
	return big_get(0, 0, r, p, u, q, v); 
}

/*
int main()
{
	int r1, c1, q;
	cin >> r1 >> c1 >> q;
	
	init(r1, c1);
	while (q--)
	{
		int type;
		cin >> type;
		
		if (type == 1)
		{
			int p, q;
			long long k;
			cin >> p >> q >> k;
			
			update(p, q, k);
		}
		
		else 
		{
			int p, q, u, v;
			cin >> p >> q >> u >> v;
			
			cout << calculate(p, q, u, v) << endl; 
		}
	}
}
*/

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	0 ms	364 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	584 ms	10584 KB	Output is correct
5	Correct	465 ms	10584 KB	Output is correct
6	Correct	499 ms	7260 KB	Output is correct
7	Correct	550 ms	7128 KB	Output is correct
8	Correct	391 ms	5468 KB	Output is correct
9	Correct	542 ms	7000 KB	Output is correct
10	Correct	495 ms	6620 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1008 ms	12908 KB	Output is correct
13	Correct	1657 ms	5092 KB	Output is correct
14	Correct	355 ms	1132 KB	Output is correct
15	Correct	1932 ms	6660 KB	Output is correct
16	Correct	313 ms	13676 KB	Output is correct
17	Correct	812 ms	8940 KB	Output is correct
18	Correct	1448 ms	14312 KB	Output is correct
19	Correct	1138 ms	14324 KB	Output is correct
20	Correct	1062 ms	13676 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	0 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	611 ms	10460 KB	Output is correct
13	Correct	459 ms	10692 KB	Output is correct
14	Correct	540 ms	7520 KB	Output is correct
15	Correct	567 ms	7128 KB	Output is correct
16	Correct	381 ms	5664 KB	Output is correct
17	Correct	535 ms	6988 KB	Output is correct
18	Correct	542 ms	6748 KB	Output is correct
19	Correct	1010 ms	13036 KB	Output is correct
20	Correct	1616 ms	4848 KB	Output is correct
21	Correct	357 ms	1132 KB	Output is correct
22	Correct	1922 ms	6572 KB	Output is correct
23	Correct	301 ms	13804 KB	Output is correct
24	Correct	850 ms	8940 KB	Output is correct
25	Correct	1344 ms	14280 KB	Output is correct
26	Correct	1184 ms	14188 KB	Output is correct
27	Correct	1098 ms	13872 KB	Output is correct
28	Correct	1183 ms	151600 KB	Output is correct
29	Correct	2116 ms	171200 KB	Output is correct
30	Correct	5378 ms	123872 KB	Output is correct
31	Correct	5222 ms	101564 KB	Output is correct
32	Correct	908 ms	10476 KB	Output is correct
33	Correct	1054 ms	13004 KB	Output is correct
34	Correct	961 ms	165560 KB	Output is correct
35	Correct	1427 ms	90780 KB	Output is correct
36	Correct	2624 ms	169616 KB	Output is correct
37	Correct	2288 ms	169492 KB	Output is correct
38	Correct	2282 ms	168900 KB	Output is correct
39	Correct	1948 ms	132940 KB	Output is correct
40	Correct	1 ms	364 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	579 ms	10716 KB	Output is correct
13	Correct	473 ms	10712 KB	Output is correct
14	Correct	499 ms	7256 KB	Output is correct
15	Correct	577 ms	7384 KB	Output is correct
16	Correct	386 ms	5468 KB	Output is correct
17	Correct	525 ms	7000 KB	Output is correct
18	Correct	502 ms	6748 KB	Output is correct
19	Correct	1006 ms	13100 KB	Output is correct
20	Correct	1612 ms	5100 KB	Output is correct
21	Correct	356 ms	1132 KB	Output is correct
22	Correct	1920 ms	6704 KB	Output is correct
23	Correct	312 ms	13804 KB	Output is correct
24	Correct	809 ms	9148 KB	Output is correct
25	Correct	1313 ms	14444 KB	Output is correct
26	Correct	1151 ms	14572 KB	Output is correct
27	Correct	1070 ms	13804 KB	Output is correct
28	Correct	1126 ms	151568 KB	Output is correct
29	Correct	2105 ms	171788 KB	Output is correct
30	Correct	5365 ms	124136 KB	Output is correct
31	Correct	5144 ms	101732 KB	Output is correct
32	Correct	866 ms	10476 KB	Output is correct
33	Correct	1020 ms	12764 KB	Output is correct
34	Correct	942 ms	165696 KB	Output is correct
35	Correct	1432 ms	90708 KB	Output is correct
36	Correct	2616 ms	169800 KB	Output is correct
37	Correct	2363 ms	169524 KB	Output is correct
38	Correct	2267 ms	169232 KB	Output is correct
39	Runtime error	1525 ms	256000 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-