답안 #29139 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29139	2017-07-18T11:22:31 Z	nibnalin	게임 (IOI13_game)	C++14	63 / 100	3613 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);
	}
}

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

#	결과	메모리	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	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

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

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

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

답안 #29139

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