답안 #29158 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29158	2017-07-18T11:51:21 Z	nibnalin	게임 (IOI13_game)	C++14	63 / 100	3596 ms	256000 KB

game

#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

#	결과	메모리	Grader output
1	Correct	2024 KB	Output is correct
2	Correct	2156 KB	Output is correct
3	Correct	2156 KB	Output is correct
4	Correct	2024 KB	Output is correct
5	Correct	2024 KB	Output is correct
6	Correct	2156 KB	Output is correct
7	Correct	2024 KB	Output is correct
8	Correct	2024 KB	Output is correct
9	Correct	2156 KB	Output is correct
10	Correct	2024 KB	Output is correct
11	Correct	2024 KB	Output is correct
12	Correct	2024 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #29158

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0