oj.uz

Submission #30613

# Submission time Handle Problem Language Result Execution time Memory
30613 2017-07-25T12:30:06 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(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, 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 1776 ms 4004 KB Output is correct
5 Correct 539 ms 4004 KB Output is correct
6 Correct 3079 ms 4004 KB Output is correct
7 Correct 4159 ms 4004 KB Output is correct
8 Correct 2759 ms 3080 KB Output is correct
9 Correct 3866 ms 4004 KB Output is correct
10 Correct 2843 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 2136 ms 5720 KB Output is correct
13 Correct 8509 ms 4136 KB Output is correct
14 Correct 659 ms 2156 KB Output is correct
15 Correct 8953 ms 4796 KB Output is correct
16 Correct 553 ms 6644 KB Output is correct
17 Correct 5476 ms 4532 KB Output is correct
18 Correct 8909 ms 6644 KB Output is correct
19 Correct 7149 ms 6644 KB Output is correct
20 Correct 6923 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 1576 ms 4004 KB Output is correct
13 Correct 609 ms 4004 KB Output is correct
14 Correct 3636 ms 4004 KB Output is correct
15 Correct 3906 ms 4004 KB Output is correct
16 Correct 2596 ms 3080 KB Output is correct
17 Correct 3969 ms 4004 KB Output is correct
18 Correct 3089 ms 4004 KB Output is correct
19 Correct 2369 ms 5720 KB Output is correct
20 Correct 8256 ms 4136 KB Output is correct
21 Correct 736 ms 2156 KB Output is correct
22 Correct 9049 ms 4796 KB Output is correct
23 Correct 499 ms 6644 KB Output is correct
24 Correct 5053 ms 4532 KB Output is correct
25 Correct 9346 ms 6644 KB Output is correct
26 Correct 7513 ms 6644 KB Output is correct
27 Correct 7529 ms 6644 KB Output is correct
28 Correct 2676 ms 22088 KB Output is correct
29 Correct 3953 ms 22088 KB Output is correct
30 Correct 10549 ms 18128 KB Output is correct
31 Correct 9196 ms 14168 KB Output is correct
32 Correct 949 ms 2156 KB Output is correct
33 Correct 1796 ms 2552 KB Output is correct
34 Correct 869 ms 22088 KB Output is correct
35 Correct 6316 ms 12056 KB Output is correct
36 Correct 12526 ms 22088 KB Output is correct
37 Correct 8856 ms 22088 KB Output is correct
38 Correct 9919 ms 22088 KB Output is correct
39 Correct 8103 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 1676 ms 4004 KB Output is correct
13 Correct 629 ms 4004 KB Output is correct
14 Correct 3256 ms 4004 KB Output is correct
15 Correct 3746 ms 4004 KB Output is correct
16 Correct 2626 ms 3080 KB Output is correct
17 Correct 3963 ms 4004 KB Output is correct
18 Correct 3256 ms 4004 KB Output is correct
19 Correct 2326 ms 5720 KB Output is correct
20 Correct 7339 ms 4136 KB Output is correct
21 Correct 646 ms 2156 KB Output is correct
22 Correct 8273 ms 4796 KB Output is correct
23 Correct 606 ms 6644 KB Output is correct
24 Correct 5669 ms 4532 KB Output is correct
25 Correct 10116 ms 6644 KB Output is correct
26 Correct 7839 ms 6644 KB Output is correct
27 Correct 7689 ms 6644 KB Output is correct
28 Correct 2809 ms 22088 KB Output is correct
29 Correct 3769 ms 22088 KB Output is correct
30 Correct 10976 ms 18128 KB Output is correct
31 Correct 8459 ms 14168 KB Output is correct
32 Correct 959 ms 2156 KB Output is correct
33 Correct 1963 ms 2552 KB Output is correct
34 Correct 669 ms 22088 KB Output is correct
35 Correct 5416 ms 12056 KB Output is correct
36 Correct 11273 ms 22088 KB Output is correct
37 Correct 8796 ms 22088 KB Output is correct
38 Correct 9743 ms 22088 KB Output is correct
39 Correct 3016 ms 45320 KB Output is correct
40 Correct 6246 ms 45320 KB Output is correct
41 Execution timed out 13000 ms 36212 KB Execution timed out
42 Halted 0 ms 0 KB -