oj.uz

Submission #30614

# Submission time Handle Problem Language Result Execution time Memory
30614 2017-07-25T12:32:45 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 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(t);
}

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

bool deltaval(pnode0& t, int k, lli val)
{
	if(!t) return 0;
	bool ret = 0;
	if(t->key == k)
	{
		t->self = val;
		ret = 1;
	}
	else if(t->key < k) ret = deltaval(t->r, k, val);
	else ret = deltaval(t->l, k, val);
	if(ret) upd(t);
	return ret;
}

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)
{
	if(deltaval(root, idx, v)) return;

	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 1453 ms 4004 KB Output is correct
5 Correct 716 ms 4004 KB Output is correct
6 Correct 2443 ms 4004 KB Output is correct
7 Correct 3203 ms 4004 KB Output is correct
8 Correct 1973 ms 3080 KB Output is correct
9 Correct 3129 ms 4004 KB Output is correct
10 Correct 2279 ms 4004 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 1923 ms 5720 KB Output is correct
13 Correct 6616 ms 4136 KB Output is correct
14 Correct 819 ms 2156 KB Output is correct
15 Correct 7569 ms 4796 KB Output is correct
16 Correct 523 ms 6644 KB Output is correct
17 Correct 4746 ms 4532 KB Output is correct
18 Correct 7063 ms 6644 KB Output is correct
19 Correct 6816 ms 6644 KB Output is correct
20 Correct 5963 ms 6644 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 1533 ms 4004 KB Output is correct
13 Correct 589 ms 4004 KB Output is correct
14 Correct 2649 ms 4004 KB Output is correct
15 Correct 3119 ms 4004 KB Output is correct
16 Correct 1969 ms 3080 KB Output is correct
17 Correct 2653 ms 4004 KB Output is correct
18 Correct 2149 ms 4004 KB Output is correct
19 Correct 2056 ms 5720 KB Output is correct
20 Correct 7046 ms 4136 KB Output is correct
21 Correct 746 ms 2156 KB Output is correct
22 Correct 7143 ms 4796 KB Output is correct
23 Correct 386 ms 6644 KB Output is correct
24 Correct 3709 ms 4532 KB Output is correct
25 Correct 6406 ms 6644 KB Output is correct
26 Correct 6333 ms 6644 KB Output is correct
27 Correct 5889 ms 6644 KB Output is correct
28 Correct 2709 ms 22088 KB Output is correct
29 Correct 3799 ms 22088 KB Output is correct
30 Correct 8689 ms 18128 KB Output is correct
31 Correct 7716 ms 14168 KB Output is correct
32 Correct 1002 ms 2156 KB Output is correct
33 Correct 1656 ms 2552 KB Output is correct
34 Correct 736 ms 22088 KB Output is correct
35 Correct 5133 ms 12056 KB Output is correct
36 Correct 10446 ms 22088 KB Output is correct
37 Correct 6453 ms 22088 KB Output is correct
38 Correct 6886 ms 22088 KB Output is correct
39 Correct 5629 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 1559 ms 4004 KB Output is correct
13 Correct 496 ms 4004 KB Output is correct
14 Correct 2253 ms 4004 KB Output is correct
15 Correct 3153 ms 4004 KB Output is correct
16 Correct 1866 ms 3080 KB Output is correct
17 Correct 3146 ms 4004 KB Output is correct
18 Correct 2183 ms 4004 KB Output is correct
19 Correct 1986 ms 5720 KB Output is correct
20 Correct 6866 ms 4136 KB Output is correct
21 Correct 726 ms 2156 KB Output is correct
22 Correct 6989 ms 4796 KB Output is correct
23 Correct 559 ms 6644 KB Output is correct
24 Correct 4706 ms 4532 KB Output is correct
25 Correct 6186 ms 6644 KB Output is correct
26 Correct 5553 ms 6644 KB Output is correct
27 Correct 5786 ms 6644 KB Output is correct
28 Correct 2573 ms 22088 KB Output is correct
29 Correct 3213 ms 22088 KB Output is correct
30 Correct 8426 ms 18128 KB Output is correct
31 Correct 7626 ms 14168 KB Output is correct
32 Correct 969 ms 2156 KB Output is correct
33 Correct 1643 ms 2552 KB Output is correct
34 Correct 756 ms 22088 KB Output is correct
35 Correct 4609 ms 12056 KB Output is correct
36 Correct 8259 ms 22088 KB Output is correct
37 Correct 6563 ms 22088 KB Output is correct
38 Correct 6896 ms 22088 KB Output is correct
39 Correct 3349 ms 45320 KB Output is correct
40 Correct 6339 ms 45320 KB Output is correct
41 Execution timed out 13000 ms 36476 KB Execution timed out
42 Halted 0 ms 0 KB -