oj.uz

Submission #30601

# Submission time Handle Problem Language Result Execution time Memory
30601 2017-07-25T11:52:03 Z nibnalin Game (IOI13_game) C++14
10 / 100
 13000 ms 9020 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include "game.h"
using namespace std;

typedef long long int lli;

long long gcd2(long long X, long long Y) {
	long long tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}

struct ppnode0 {
	lli key, prior, self, v;
	ppnode0 *l, *r;
	ppnode0(lli _key = 0, lli _self = 0, lli _v = 0, 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:0);
}

void upd(pnode0& t)
{
	if(t)
	{
		t->v = t->self;
		t->v = gcd2(t->v, gcd2(getv(t->l), getv(t->r)));
	}
}

void split(pnode0 t, pnode0& L, pnode0& R, lli k)
{
	upd(t), upd(L), upd(R);
	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), upd(L), upd(R);
}

void merge(pnode0& t, pnode0 L, pnode0 R)
{
	upd(t), upd(L), upd(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), upd(L), upd(R);
}

/* lli findval(pnode0& t, lli k)
{
	if(!t) return 0;
	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, lli a, lli 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, lli L, lli R, lli a, lli b, lli c, lli d)
{
	if(a > R || b < L || !root) return 0;
	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, lli 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, lli L, lli R, lli a, lli 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?qry0(root->l->v, b, b):0), q = (root->r?qry0(root->r->v, b, b):0);
		upd0(root->v, b, gcd2(p, q));
	}
	//cout << L << " " << R << " " << root->v->v << "\n";
}

lli r, c;
pnode1 grid;

void init(int _R, int _C)
{
	//cout << "init\n";
	r = _R-1;
	c = _C-1;
	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 6 ms 2156 KB Output is correct
3 Correct 6 ms 2156 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 6 ms 2156 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct
9 Correct 6 ms 2024 KB Output is correct
10 Correct 3 ms 2024 KB Output is correct
11 Correct 3 ms 2024 KB Output is correct
12 Correct 0 ms 2024 KB Output is correct

Subtask #2
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 4996 ms 4796 KB Output is correct
5 Correct 1709 ms 4796 KB Output is correct
6 Correct 12446 ms 4796 KB Output is correct
7 Execution timed out 13000 ms 4796 KB Execution timed out
8 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 9 ms 2156 KB Output is correct
3 Correct 6 ms 2156 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 6 ms 2156 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct
9 Correct 6 ms 2024 KB Output is correct
10 Correct 3 ms 2024 KB Output is correct
11 Correct 3 ms 2024 KB Output is correct
12 Correct 5889 ms 9020 KB Output is correct
13 Execution timed out 13000 ms 8228 KB Execution timed out
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 9 ms 2156 KB Output is correct
3 Correct 6 ms 2156 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 6 ms 2156 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct
9 Correct 6 ms 2024 KB Output is correct
10 Correct 3 ms 2024 KB Output is correct
11 Correct 3 ms 2024 KB Output is correct
12 Correct 4656 ms 4796 KB Output is correct
13 Correct 1646 ms 4796 KB Output is correct
14 Correct 12309 ms 4796 KB Output is correct
15 Execution timed out 13000 ms 4796 KB Execution timed out
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 6 ms 2156 KB Output is correct
3 Correct 6 ms 2156 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 6 ms 2156 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct
9 Correct 6 ms 2024 KB Output is correct
10 Correct 3 ms 2024 KB Output is correct
11 Correct 3 ms 2024 KB Output is correct
12 Correct 4673 ms 4796 KB Output is correct
13 Correct 1756 ms 4796 KB Output is correct
14 Correct 12246 ms 4796 KB Output is correct
15 Execution timed out 13000 ms 4796 KB Execution timed out
16 Halted 0 ms 0 KB -