답안 #29134 :: oj.uz

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

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

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

pnode1 upd1(pnode1 root, int L, int R, int a, int b, lli v)
{
	if(!root) root = new ppnode1();
	if(L == R) return new ppnode1(upd0(root->ans, 0, sz.second, b, v), NULL, NULL);
	else
	{
		pnode1 nw = new ppnode1(root->ans, NULL, NULL);
		if(a <= (L+R)/2) nw->l = upd1(root->l, L, (L+R)/2, a, b, v), nw->r = root->r;
		else nw->r = upd1(root->r, (L+R)/2+1, R, a, b, v), nw->l = root->l;
		lli pusher = 0;
		if(nw->l) pusher = gcd2(pusher, qry0(nw->l->ans, 0, sz.second, b, b));
		if(nw->r) pusher = gcd2(pusher, qry0(nw->r->ans, 0, sz.second, b, b));
		nw->ans = upd0(nw->ans, 0, sz.second, b, pusher);
		return nw;
	}
}

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

void update(int P, int Q, long long K) {
	//cout << "upd\n";
	grid = 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	2420 KB	Output is correct
3	Correct	2420 KB	Output is correct
4	Correct	2024 KB	Output is correct
5	Correct	2024 KB	Output is correct
6	Correct	2420 KB	Output is correct
7	Correct	2024 KB	Output is correct
8	Correct	2024 KB	Output is correct
9	Correct	2288 KB	Output is correct
10	Correct	2156 KB	Output is correct
11	Correct	2156 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	993 ms	35816 KB	Output is correct
5	Correct	563 ms	35816 KB	Output is correct
6	Correct	946 ms	36212 KB	Output is correct
7	Correct	1149 ms	36212 KB	Output is correct
8	Correct	733 ms	19184 KB	Output is correct
9	Correct	1096 ms	36212 KB	Output is correct
10	Correct	1106 ms	36212 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	2420 KB	Output is correct
3	Correct	0 ms	2420 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	2420 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	2288 KB	Output is correct
10	Correct	0 ms	2156 KB	Output is correct
11	Correct	0 ms	2156 KB	Output is correct
12	Correct	1646 ms	54560 KB	Output is correct
13	Correct	3276 ms	48224 KB	Output is correct
14	Correct	599 ms	50600 KB	Output is correct
15	Correct	3726 ms	58256 KB	Output is correct
16	Correct	483 ms	67760 KB	Output is correct
17	Correct	2069 ms	35024 KB	Output is correct
18	Correct	3136 ms	67760 KB	Output is correct
19	Correct	3043 ms	67760 KB	Output is correct
20	Correct	2786 ms	67760 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	2420 KB	Output is correct
3	Correct	0 ms	2420 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	2420 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	2288 KB	Output is correct
10	Correct	0 ms	2156 KB	Output is correct
11	Correct	0 ms	2156 KB	Output is correct
12	Correct	1039 ms	35816 KB	Output is correct
13	Correct	663 ms	35816 KB	Output is correct
14	Correct	1089 ms	36212 KB	Output is correct
15	Correct	1106 ms	36212 KB	Output is correct
16	Correct	609 ms	19184 KB	Output is correct
17	Correct	1116 ms	36212 KB	Output is correct
18	Correct	1036 ms	36212 KB	Output is correct
19	Correct	1616 ms	54560 KB	Output is correct
20	Correct	3126 ms	48224 KB	Output is correct
21	Correct	636 ms	50600 KB	Output is correct
22	Correct	3669 ms	58256 KB	Output is correct
23	Correct	366 ms	67760 KB	Output is correct
24	Correct	2246 ms	35024 KB	Output is correct
25	Correct	3539 ms	67760 KB	Output is correct
26	Correct	2166 ms	67760 KB	Output is correct
27	Correct	2826 ms	67760 KB	Output is correct
28	Memory limit exceeded	683 ms	256000 KB	Memory limit exceeded
29	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	2420 KB	Output is correct
3	Correct	0 ms	2420 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	2420 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	2288 KB	Output is correct
10	Correct	0 ms	2156 KB	Output is correct
11	Correct	0 ms	2156 KB	Output is correct
12	Correct	1126 ms	35816 KB	Output is correct
13	Correct	703 ms	35816 KB	Output is correct
14	Correct	1086 ms	36212 KB	Output is correct
15	Correct	1313 ms	36212 KB	Output is correct
16	Correct	679 ms	19184 KB	Output is correct
17	Correct	1169 ms	36212 KB	Output is correct
18	Correct	1126 ms	36212 KB	Output is correct
19	Correct	1656 ms	54560 KB	Output is correct
20	Correct	3129 ms	48224 KB	Output is correct
21	Correct	599 ms	50600 KB	Output is correct
22	Correct	3729 ms	58256 KB	Output is correct
23	Correct	489 ms	67760 KB	Output is correct
24	Correct	1976 ms	35024 KB	Output is correct
25	Correct	3519 ms	67760 KB	Output is correct
26	Correct	2543 ms	67760 KB	Output is correct
27	Correct	1986 ms	67760 KB	Output is correct
28	Memory limit exceeded	649 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

답안 #29134

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