oj.uz

Submission #30620

# Submission time Handle Problem Language Result Execution time Memory
30620 2017-07-25T12:48:13 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, ppnode0*_l = NULL, ppnode0*_r = NULL)
	{
		key = _key, self = _self, v = _self, 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);
}

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 vv)
{
	pnode0 part1 = NULL, part2 = NULL, part3 = NULL, part4 = NULL;
	split(root, part1, part2, idx);
	split(part1, part3, part4, idx-1);
	if(!part4) part4 = new ppnode0(idx, vv);
	else part4->self = part4->v = vv;
	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 1379 ms 4004 KB Output is correct
5 Correct 686 ms 4004 KB Output is correct
6 Correct 2353 ms 4004 KB Output is correct
7 Correct 2743 ms 4004 KB Output is correct
8 Correct 1876 ms 3080 KB Output is correct
9 Correct 2736 ms 4004 KB Output is correct
10 Correct 2323 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 2286 ms 5720 KB Output is correct
13 Correct 7219 ms 4136 KB Output is correct
14 Correct 769 ms 2156 KB Output is correct
15 Correct 7513 ms 4796 KB Output is correct
16 Correct 413 ms 6644 KB Output is correct
17 Correct 4213 ms 4532 KB Output is correct
18 Correct 7013 ms 6644 KB Output is correct
19 Correct 5736 ms 6644 KB Output is correct
20 Correct 5649 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 1383 ms 4004 KB Output is correct
13 Correct 743 ms 4004 KB Output is correct
14 Correct 2456 ms 4004 KB Output is correct
15 Correct 3149 ms 4004 KB Output is correct
16 Correct 2019 ms 3080 KB Output is correct
17 Correct 3179 ms 4004 KB Output is correct
18 Correct 2599 ms 4004 KB Output is correct
19 Correct 2259 ms 5720 KB Output is correct
20 Correct 6909 ms 4136 KB Output is correct
21 Correct 719 ms 2156 KB Output is correct
22 Correct 7596 ms 4796 KB Output is correct
23 Correct 579 ms 6644 KB Output is correct
24 Correct 3829 ms 4532 KB Output is correct
25 Correct 8143 ms 6644 KB Output is correct
26 Correct 7306 ms 6644 KB Output is correct
27 Correct 5753 ms 6644 KB Output is correct
28 Correct 2456 ms 22088 KB Output is correct
29 Correct 3543 ms 22088 KB Output is correct
30 Correct 9059 ms 18128 KB Output is correct
31 Correct 8409 ms 14168 KB Output is correct
32 Correct 1049 ms 2156 KB Output is correct
33 Correct 1696 ms 2552 KB Output is correct
34 Correct 743 ms 22088 KB Output is correct
35 Correct 5109 ms 12056 KB Output is correct
36 Correct 9283 ms 22088 KB Output is correct
37 Correct 7223 ms 22088 KB Output is correct
38 Correct 6773 ms 22088 KB Output is correct
39 Correct 5763 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 1549 ms 4004 KB Output is correct
13 Correct 629 ms 4004 KB Output is correct
14 Correct 2486 ms 4004 KB Output is correct
15 Correct 3276 ms 4004 KB Output is correct
16 Correct 1959 ms 3080 KB Output is correct
17 Correct 2793 ms 4004 KB Output is correct
18 Correct 2003 ms 4004 KB Output is correct
19 Correct 2069 ms 5720 KB Output is correct
20 Correct 6726 ms 4136 KB Output is correct
21 Correct 813 ms 2156 KB Output is correct
22 Correct 7286 ms 4796 KB Output is correct
23 Correct 436 ms 6644 KB Output is correct
24 Correct 4006 ms 4532 KB Output is correct
25 Correct 6423 ms 6644 KB Output is correct
26 Correct 6686 ms 6644 KB Output is correct
27 Correct 6603 ms 6644 KB Output is correct
28 Correct 2503 ms 22088 KB Output is correct
29 Correct 3176 ms 22088 KB Output is correct
30 Correct 8753 ms 18128 KB Output is correct
31 Correct 7756 ms 14168 KB Output is correct
32 Correct 966 ms 2156 KB Output is correct
33 Correct 1763 ms 2552 KB Output is correct
34 Correct 956 ms 22088 KB Output is correct
35 Correct 5319 ms 12056 KB Output is correct
36 Correct 7919 ms 22088 KB Output is correct
37 Correct 6923 ms 22088 KB Output is correct
38 Correct 6996 ms 22088 KB Output is correct
39 Correct 3086 ms 45320 KB Output is correct
40 Correct 5476 ms 45320 KB Output is correct
41 Execution timed out 13000 ms 36476 KB Execution timed out
42 Halted 0 ms 0 KB -