oj.uz

답안 #390253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390253 2021-04-15T16:12:54 Z rainboy 게임 (IOI13_game) C
10 / 100
 13000 ms 6796 KB 
#include "game.h"

#define LG	30	/* LG = ceil(log2(10^9)) */
#define NU	22000
#define N	(NU * (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 + N]; int ul[1 + N], ur[1 + N], dl[1 + N], dr[1 + N], t_, _ = 1;

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

int update_(int t, int il, int ir, int jl, int jr, int i, int j, long long x) {
	if (t == 0)
		t = _++;
	if (ir - il == 1 && jr - jl == 1)
		xx[t] = x;
	else {
		int im = (il + ir) / 2, jm = (jl + jr) / 2;

		if (i < im && j < jm)
			ul[t] = update_(ul[t], il, im, jl, jm, i, j, x);
		else if (i < im && j >= jm)
			ur[t] = update_(ur[t], il, im, jm, jr, i, j, x);
		else if (i >= im && j < jm)
			dl[t] = update_(dl[t], im, ir, jl, jm, i, j, x);
		else
			dr[t] = update_(dr[t], im, ir, jm, jr, i, j, x);
		xx[t] = gcd(gcd(gcd(xx[ul[t]], xx[ur[t]]), xx[dl[t]]), xx[dr[t]]);
	}
	return t;
}

long long ans;

void query_(int t, int il, int ir, int jl, int jr, int i1, int i2, int j1, int j2) {
	int im, jm;

	if (i2 <= il || ir <= i1 || j2 <= jl || jr <= j1)
		return;
	if (i1 <= il && ir <= i2 && j1 <= jl && jr <= j2) {
		ans = gcd(ans, xx[t]);
		return;
	}
	im = (il + ir) / 2, jm = (jl + jr) / 2;
	query_(ul[t], il, im, jl, jm, i1, i2, j1, j2);
	query_(ur[t], il, im, jm, jr, i1, i2, j1, j2);
	query_(dl[t], im, ir, jl, jm, i1, i2, j1, j2);
	query_(dr[t], im, ir, jm, jr, i1, i2, j1, j2);
}

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

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 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 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Execution timed out 13053 ms 572 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Execution timed out 13056 ms 6796 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 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 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Execution timed out 13069 ms 872 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 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 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Execution timed out 13101 ms 580 KB Time limit exceeded
13 Halted 0 ms 0 KB -