oj.uz

Submission #29158

# Submission time Handle Problem Language Result Execution time Memory
29158 2017-07-18T11:51:21 Z nibnalin Game (IOI13_game) C++14
63 / 100
 3596 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);
	}
}


void upd0_fast(pnode0& root, int L, int R, int b, pnode0 rootl, pnode0 rootr)
{
	if(L == R)
	{
		root->ans = 0ll;
		if(rootl) root->ans = gcd2(rootl->ans, root->ans);
		if(rootr) root->ans = gcd2(rootr->ans, root->ans);
	}
	else
	{
		if(b <= (L+R)/2)
		{
			if(!root->l) root->l = new ppnode0();
			upd0_fast(root->l, L, (L+R)/2, b, (rootl?rootl->l:NULL), (rootr?rootr->l:NULL));
		}
		else
		{
			if(!root->r) root->r = new ppnode0();
			upd0_fast(root->r, (L+R)/2+1, R, b, (rootl?rootl->r:NULL), (rootr?rootr->r:NULL));
		}
		root->ans = 0ll;
		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);*/

		upd0_fast(root->ans, 0, sz.second, b, (root->l?root->l->ans:NULL), (root->r?root->r->ans:NULL));
	}
}
 
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 929 ms 10340 KB Output is correct
5 Correct 619 ms 10340 KB Output is correct
6 Correct 859 ms 10472 KB Output is correct
7 Correct 1139 ms 10472 KB Output is correct
8 Correct 649 ms 6776 KB Output is correct
9 Correct 1079 ms 10604 KB Output is correct
10 Correct 969 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 1343 ms 13508 KB Output is correct
13 Correct 2906 ms 7172 KB Output is correct
14 Correct 429 ms 2156 KB Output is correct
15 Correct 3596 ms 9680 KB Output is correct
16 Correct 296 ms 19184 KB Output is correct
17 Correct 1673 ms 11924 KB Output is correct
18 Correct 2919 ms 19184 KB Output is correct
19 Correct 2629 ms 19316 KB Output is correct
20 Correct 1889 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 849 ms 10340 KB Output is correct
13 Correct 543 ms 10340 KB Output is correct
14 Correct 923 ms 10472 KB Output is correct
15 Correct 843 ms 10472 KB Output is correct
16 Correct 673 ms 6776 KB Output is correct
17 Correct 1106 ms 10604 KB Output is correct
18 Correct 933 ms 10472 KB Output is correct
19 Correct 1359 ms 13508 KB Output is correct
20 Correct 3119 ms 7172 KB Output is correct
21 Correct 433 ms 2156 KB Output is correct
22 Correct 3409 ms 9680 KB Output is correct
23 Correct 243 ms 19184 KB Output is correct
24 Correct 1763 ms 11924 KB Output is correct
25 Correct 2629 ms 19184 KB Output is correct
26 Correct 2466 ms 19316 KB Output is correct
27 Correct 1853 ms 19184 KB Output is correct
28 Correct 1679 ms 252296 KB Output is correct
29 Memory limit exceeded 2829 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 983 ms 10340 KB Output is correct
13 Correct 623 ms 10340 KB Output is correct
14 Correct 863 ms 10472 KB Output is correct
15 Correct 1026 ms 10472 KB Output is correct
16 Correct 643 ms 6776 KB Output is correct
17 Correct 1022 ms 10604 KB Output is correct
18 Correct 989 ms 10472 KB Output is correct
19 Correct 1379 ms 13508 KB Output is correct
20 Correct 3029 ms 7172 KB Output is correct
21 Correct 429 ms 2156 KB Output is correct
22 Correct 3519 ms 9680 KB Output is correct
23 Correct 249 ms 19184 KB Output is correct
24 Correct 1636 ms 11924 KB Output is correct
25 Correct 3099 ms 19184 KB Output is correct
26 Correct 2156 ms 19316 KB Output is correct
27 Correct 1679 ms 19184 KB Output is correct
28 Correct 1189 ms 252296 KB Output is correct
29 Memory limit exceeded 2616 ms 256000 KB Memory limit exceeded
30 Halted 0 ms 0 KB -