oj.uz

Submission #29139

# Submission time Handle Problem Language Result Execution time Memory
29139 2017-07-18T11:22:31 Z nibnalin Game (IOI13_game) C++14
63 / 100
 3613 ms 256000 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include "game.h"
using namespace std;

typedef long long lli;

struct ppnode0 {
	lli ans;
	ppnode0 *l, *r;
	ppnode0(lli _res = 0ll, ppnode0 *_l = NULL, ppnode0 *_r = NULL)
	{
		ans = _res, l = _l, r = _r;
	}
};

struct ppnode1 {
	ppnode0* ans;
	ppnode1 *l, *r;
	ppnode1(ppnode0* _res = new ppnode0(), ppnode1 *_l = NULL, ppnode1 *_r = NULL)
	{
		ans = _res, l = _l, r = _r;
	}
};

typedef ppnode0* pnode0;
typedef ppnode1* pnode1;

pair<int, int> sz;
pnode1 grid;

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;
}

void upd0(pnode0& root, int L, int R, int b, lli v)
{
	if(L == R) root->ans = v;
	else
	{
		if(b <= (L+R)/2)
		{
			if(!root->l) root->l = new ppnode0();
			upd0(root->l, L, (L+R)/2, b, v);
		}
		else
		{
			if(!root->r) root->r = new ppnode0();
			upd0(root->r, (L+R)/2+1, R, b, v);
		}
		root->ans = 0;
		if(root->l) root->ans = gcd2(root->ans, root->l->ans);
		if(root->r) root->ans = gcd2(root->ans, root->r->ans);
	}
}

lli qry0(pnode0 root, int L, int R, int a, int b)
{
	if(a > R || b < L || !root) return 0ll;
	else if(a <= L && R <= b) return root->ans;
	else return gcd2(qry0(root->l, L, (L+R)/2, a, b), qry0(root->r, (L+R)/2+1, R, a, b));
}

void upd1(pnode1& root, int L, int R, int a, int b, lli v)
{
	if(L == R) upd0(root->ans, 0, sz.second, 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 pusher = 0;
		if(root->l) pusher = gcd2(pusher, qry0(root->l->ans, 0, sz.second, b, b));
		if(root->r) pusher = gcd2(pusher, qry0(root->r->ans, 0, sz.second, b, b));
		upd0(root->ans, 0, sz.second, b, pusher);
	}
}

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->ans, 0, sz.second, 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 init(int _R, int _C) {
	sz.first = _R-1, sz.second = _C-1;
	grid = new ppnode1();
}

void update(int P, int Q, long long K) {
	//cout << "upd\n";
	upd1(grid, 0, sz.first, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
	//cout << "calc\n";
	return qry1(grid, 0, sz.first, 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 2156 KB Output is correct
3 Correct 0 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 0 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 0 ms 2156 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 899 ms 10340 KB Output is correct
5 Correct 606 ms 10340 KB Output is correct
6 Correct 793 ms 10472 KB Output is correct
7 Correct 969 ms 10472 KB Output is correct
8 Correct 619 ms 6776 KB Output is correct
9 Correct 859 ms 10604 KB Output is correct
10 Correct 883 ms 10472 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 2156 KB Output is correct
3 Correct 0 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 0 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 0 ms 2156 KB Output is correct
10 Correct 0 ms 2024 KB Output is correct
11 Correct 0 ms 2024 KB Output is correct
12 Correct 1449 ms 13508 KB Output is correct
13 Correct 3026 ms 7172 KB Output is correct
14 Correct 516 ms 2156 KB Output is correct
15 Correct 3469 ms 9680 KB Output is correct
16 Correct 376 ms 19184 KB Output is correct
17 Correct 1919 ms 11924 KB Output is correct
18 Correct 3226 ms 19184 KB Output is correct
19 Correct 2809 ms 19316 KB Output is correct
20 Correct 2529 ms 19184 KB Output is correct
21 Correct 0 ms 2024 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2156 KB Output is correct
3 Correct 0 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 0 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 0 ms 2156 KB Output is correct
10 Correct 0 ms 2024 KB Output is correct
11 Correct 0 ms 2024 KB Output is correct
12 Correct 909 ms 10340 KB Output is correct
13 Correct 613 ms 10340 KB Output is correct
14 Correct 1022 ms 10472 KB Output is correct
15 Correct 1113 ms 10472 KB Output is correct
16 Correct 629 ms 6776 KB Output is correct
17 Correct 1079 ms 10604 KB Output is correct
18 Correct 939 ms 10472 KB Output is correct
19 Correct 1496 ms 13508 KB Output is correct
20 Correct 3193 ms 7172 KB Output is correct
21 Correct 446 ms 2156 KB Output is correct
22 Correct 3613 ms 9680 KB Output is correct
23 Correct 303 ms 19184 KB Output is correct
24 Correct 1679 ms 11924 KB Output is correct
25 Correct 3203 ms 19184 KB Output is correct
26 Correct 2556 ms 19316 KB Output is correct
27 Correct 2529 ms 19184 KB Output is correct
28 Correct 1746 ms 252296 KB Output is correct
29 Memory limit exceeded 3196 ms 256000 KB Memory limit exceeded
30 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 0 ms 2156 KB Output is correct
3 Correct 0 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 0 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 0 ms 2156 KB Output is correct
10 Correct 0 ms 2024 KB Output is correct
11 Correct 0 ms 2024 KB Output is correct
12 Correct 906 ms 10340 KB Output is correct
13 Correct 563 ms 10340 KB Output is correct
14 Correct 839 ms 10472 KB Output is correct
15 Correct 873 ms 10472 KB Output is correct
16 Correct 583 ms 6776 KB Output is correct
17 Correct 806 ms 10604 KB Output is correct
18 Correct 859 ms 10472 KB Output is correct
19 Correct 1453 ms 13508 KB Output is correct
20 Correct 2953 ms 7172 KB Output is correct
21 Correct 446 ms 2156 KB Output is correct
22 Correct 3519 ms 9680 KB Output is correct
23 Correct 416 ms 19184 KB Output is correct
24 Correct 1646 ms 11924 KB Output is correct
25 Correct 3129 ms 19184 KB Output is correct
26 Correct 2103 ms 19316 KB Output is correct
27 Correct 2286 ms 19184 KB Output is correct
28 Correct 1759 ms 252296 KB Output is correct
29 Memory limit exceeded 3196 ms 256000 KB Memory limit exceeded
30 Halted 0 ms 0 KB -