oj.uz

답안 #390254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390254 2021-04-15T16:25:19 Z rainboy 게임 (IOI13_game) C
80 / 100
 4367 ms 256004 KB 
#include "game.h"

#define LG	30	/* LG = ceil(log2(10^9)) */
#define NU	22000
#define N1	(NU * (LG + 1))
#define N2	(NU * (LG + 1) * (LG + 1))

long long gcd(long long a, long long b) {
	return b == 0 ? a : gcd(b, a % b);
}

int r, c;
long long xx[1 + N2]; int ll_[1 + N2], rr_[1 + N2], __ = 1;
int tt[1 + N1], ll[1 + N1], rr[1 + N1], t_, _ = 1;

void init(int R, int C) {
	r = R, c = C;
}

int update2(int t, int jl, int jr, int j, long long x) {
	if (t == 0)
		t = __++;
	if (jr - jl == 1)
		xx[t] = x;
	else {
		int jm = (jl + jr) / 2;

		if (j < jm)
			ll_[t] = update2(ll_[t], jl, jm, j, x);
		else
			rr_[t] = update2(rr_[t], jm, jr, j, x);
		xx[t] = gcd(xx[ll_[t]], xx[rr_[t]]);
	}
	return t;
}

long long get(int t, int j) {
	int jl = 0, jr = c;

	while (t && jr - jl > 1) {
		int jm = (jl + jr) / 2;

		if (j < jm)
			jr = jm, t = ll_[t];
		else
			jl = jm, t = rr_[t];
	}
	return xx[t];
}

int update1(int t, int il, int ir, int i, int j, long long x) {
	if (t == 0)
		t = _++;
	if (ir - il > 1) {
		int im = (il + ir) / 2;

		if (i < im)
			ll[t] = update1(ll[t], il, im, i, j, x);
		else
			rr[t] = update1(rr[t], im, ir, i, j, x);
		x = gcd(get(tt[ll[t]], j), get(tt[rr[t]], j));
	}
	tt[t] = update2(tt[t], 0, c, j, x);
	return t;
}

long long ans;

void query2(int t, int jl, int jr, int j1, int j2) {
	int jm;

	if (j2 <= jl || jr <= j1 || t == 0)
		return;
	if (j1 <= jl && jr <= j2) {
		ans = gcd(ans, xx[t]);
		return;
	}
	jm = (jl + jr) / 2;
	query2(ll_[t], jl, jm, j1, j2);
	query2(rr_[t], jm, jr, j1, j2);
}

void query1(int t, int il, int ir, int i1, int i2, int j1, int j2) {
	int im;

	if (i2 <= il || ir <= i1 || tt[t] == 0)
		return;
	if (i1 <= il && ir <= i2) {
		query2(tt[t], 0, c, j1, j2);
		return;
	}
	im = (il + ir) / 2;
	query1(ll[t], il, im, i1, i2, j1, j2);
	query1(rr[t], im, ir, i1, i2, j1, j2);
}

void update(int i, int j, long long x) {
	t_ = update1(t_, 0, r, i, j, x);
}

long long calculate(int i1, int j1, int i2, int j2) {
	i2++, j2++;
	ans = 0, query1(t_, 0, r, i1, i2, j1, j2);
	return ans;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 565 ms 12604 KB Output is correct
5 Correct 414 ms 12700 KB Output is correct
6 Correct 419 ms 10244 KB Output is correct
7 Correct 482 ms 10064 KB Output is correct
8 Correct 318 ms 8440 KB Output is correct
9 Correct 444 ms 10176 KB Output is correct
10 Correct 426 ms 9728 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 953 ms 11272 KB Output is correct
13 Correct 1450 ms 7548 KB Output is correct
14 Correct 278 ms 5572 KB Output is correct
15 Correct 1645 ms 9228 KB Output is correct
16 Correct 222 ms 13896 KB Output is correct
17 Correct 641 ms 11364 KB Output is correct
18 Correct 1233 ms 15328 KB Output is correct
19 Correct 972 ms 15428 KB Output is correct
20 Correct 930 ms 14896 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 558 ms 12648 KB Output is correct
13 Correct 437 ms 12696 KB Output is correct
14 Correct 408 ms 10156 KB Output is correct
15 Correct 454 ms 9996 KB Output is correct
16 Correct 326 ms 8532 KB Output is correct
17 Correct 447 ms 10040 KB Output is correct
18 Correct 401 ms 9664 KB Output is correct
19 Correct 959 ms 14216 KB Output is correct
20 Correct 1391 ms 7556 KB Output is correct
21 Correct 275 ms 5492 KB Output is correct
22 Correct 1692 ms 9224 KB Output is correct
23 Correct 211 ms 13812 KB Output is correct
24 Correct 636 ms 11392 KB Output is correct
25 Correct 1098 ms 15264 KB Output is correct
26 Correct 920 ms 15352 KB Output is correct
27 Correct 873 ms 14812 KB Output is correct
28 Correct 767 ms 136048 KB Output is correct
29 Correct 2172 ms 150816 KB Output is correct
30 Correct 4357 ms 108804 KB Output is correct
31 Correct 4009 ms 84992 KB Output is correct
32 Correct 496 ms 10268 KB Output is correct
33 Correct 646 ms 11472 KB Output is correct
34 Correct 491 ms 144676 KB Output is correct
35 Correct 1330 ms 80032 KB Output is correct
36 Correct 2744 ms 148680 KB Output is correct
37 Correct 2171 ms 148920 KB Output is correct
38 Correct 2206 ms 148272 KB Output is correct
39 Correct 1788 ms 116564 KB Output is correct
40 Correct 1 ms 288 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 574 ms 12612 KB Output is correct
13 Correct 482 ms 12872 KB Output is correct
14 Correct 418 ms 10180 KB Output is correct
15 Correct 452 ms 9996 KB Output is correct
16 Correct 327 ms 8568 KB Output is correct
17 Correct 435 ms 10016 KB Output is correct
18 Correct 419 ms 9684 KB Output is correct
19 Correct 976 ms 14276 KB Output is correct
20 Correct 1410 ms 7612 KB Output is correct
21 Correct 288 ms 5500 KB Output is correct
22 Correct 1679 ms 9536 KB Output is correct
23 Correct 206 ms 13764 KB Output is correct
24 Correct 643 ms 11436 KB Output is correct
25 Correct 1118 ms 15288 KB Output is correct
26 Correct 937 ms 15516 KB Output is correct
27 Correct 887 ms 14844 KB Output is correct
28 Correct 778 ms 136048 KB Output is correct
29 Correct 2170 ms 150764 KB Output is correct
30 Correct 4367 ms 108832 KB Output is correct
31 Correct 4074 ms 84872 KB Output is correct
32 Correct 497 ms 10184 KB Output is correct
33 Correct 635 ms 11484 KB Output is correct
34 Correct 504 ms 144712 KB Output is correct
35 Correct 1392 ms 80104 KB Output is correct
36 Correct 2759 ms 148680 KB Output is correct
37 Correct 2211 ms 148832 KB Output is correct
38 Correct 2136 ms 148284 KB Output is correct
39 Runtime error 1130 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -