oj.uz

Submission #30608

# Submission time Handle Problem Language Result Execution time Memory
30608 2017-07-25T12:11:52 Z nibnalin Game (IOI13_game) C++14
80 / 100
 13000 ms 45320 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <ctime>
#include <cstdlib>
#include "game.h"
using namespace std;

typedef long long int 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, lli _v = 0ll, ppnode0*_l = NULL, ppnode0*_r = NULL)
	{
		key = _key, self = _self, v = _v, 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(L), upd(R);
}

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, lli 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 v)
{
	pnode0 part1 = NULL, part2 = NULL, part3 = NULL, part4 = NULL;
	split(root, part1, part2, idx);
	split(part1, part3, part4, idx-1);
	part4 = new ppnode0(idx, v, v, NULL, NULL);
	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

# 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 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 0 ms 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 1619 ms 4136 KB Output is correct
5 Correct 686 ms 4136 KB Output is correct
6 Correct 3293 ms 4136 KB Output is correct
7 Correct 3756 ms 4136 KB Output is correct
8 Correct 2549 ms 3080 KB Output is correct
9 Correct 3836 ms 4136 KB Output is correct
10 Correct 2849 ms 4136 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 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 2393 ms 7304 KB Output is correct
13 Correct 8966 ms 7304 KB Output is correct
14 Correct 859 ms 7700 KB Output is correct
15 Correct 9513 ms 7832 KB Output is correct
16 Correct 479 ms 7832 KB Output is correct
17 Correct 5503 ms 4796 KB Output is correct
18 Correct 10073 ms 7832 KB Output is correct
19 Correct 8386 ms 7832 KB Output is correct
20 Correct 7893 ms 7832 KB Output is correct
21 Correct 0 ms 2024 KB Output is correct

Subtask #4
17.0 / 17.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 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 1759 ms 4136 KB Output is correct
13 Correct 703 ms 4136 KB Output is correct
14 Correct 3356 ms 4136 KB Output is correct
15 Correct 4223 ms 4136 KB Output is correct
16 Correct 2639 ms 3080 KB Output is correct
17 Correct 3856 ms 4136 KB Output is correct
18 Correct 3389 ms 4136 KB Output is correct
19 Correct 2603 ms 7304 KB Output is correct
20 Correct 8699 ms 7304 KB Output is correct
21 Correct 889 ms 7700 KB Output is correct
22 Correct 8883 ms 7832 KB Output is correct
23 Correct 523 ms 7832 KB Output is correct
24 Correct 5706 ms 4796 KB Output is correct
25 Correct 10299 ms 7832 KB Output is correct
26 Correct 8506 ms 7832 KB Output is correct
27 Correct 7919 ms 7832 KB Output is correct
28 Correct 2783 ms 22088 KB Output is correct
29 Correct 3729 ms 22088 KB Output is correct
30 Correct 10936 ms 19580 KB Output is correct
31 Correct 8769 ms 18920 KB Output is correct
32 Correct 1206 ms 16544 KB Output is correct
33 Correct 2193 ms 16544 KB Output is correct
34 Correct 799 ms 22088 KB Output is correct
35 Correct 5803 ms 12056 KB Output is correct
36 Correct 10369 ms 22088 KB Output is correct
37 Correct 8506 ms 22088 KB Output is correct
38 Correct 8436 ms 22088 KB Output is correct
39 Correct 7473 ms 17336 KB Output is correct
40 Correct 0 ms 2024 KB Output is correct

Subtask #5
0 / 20.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 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 1773 ms 4136 KB Output is correct
13 Correct 636 ms 4136 KB Output is correct
14 Correct 3316 ms 4136 KB Output is correct
15 Correct 3963 ms 4136 KB Output is correct
16 Correct 2606 ms 3080 KB Output is correct
17 Correct 3713 ms 4136 KB Output is correct
18 Correct 2779 ms 4136 KB Output is correct
19 Correct 2273 ms 7304 KB Output is correct
20 Correct 8186 ms 7304 KB Output is correct
21 Correct 883 ms 7700 KB Output is correct
22 Correct 8866 ms 7832 KB Output is correct
23 Correct 673 ms 7832 KB Output is correct
24 Correct 4883 ms 4796 KB Output is correct
25 Correct 9033 ms 7832 KB Output is correct
26 Correct 8396 ms 7832 KB Output is correct
27 Correct 8223 ms 7832 KB Output is correct
28 Correct 2123 ms 22088 KB Output is correct
29 Correct 3773 ms 22088 KB Output is correct
30 Correct 10319 ms 19580 KB Output is correct
31 Correct 8889 ms 18920 KB Output is correct
32 Correct 1306 ms 16544 KB Output is correct
33 Correct 2159 ms 16544 KB Output is correct
34 Correct 863 ms 22088 KB Output is correct
35 Correct 6426 ms 12056 KB Output is correct
36 Correct 10476 ms 22088 KB Output is correct
37 Correct 9093 ms 22088 KB Output is correct
38 Correct 9003 ms 22088 KB Output is correct
39 Correct 3403 ms 45320 KB Output is correct
40 Correct 5769 ms 45320 KB Output is correct
41 Execution timed out 13000 ms 39908 KB Execution timed out
42 Halted 0 ms 0 KB -