oj.uz

답안 #97693

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97693 2019-02-17T18:02:55 Z tincamatei 게임 (IOI13_game) C++14
37 / 100
 2764 ms 257024 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

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

int R, C;
long long **aint;

void updateSmall(int anod, int poz, long long val, int l, int r, int nod = 1) {
	if(poz < l || r < poz) return;
	if(l == r)
		aint[anod][nod] = val;
	else if(l < r) {
		int mid = (l + r) / 2;
		updateSmall(anod, poz, val, l, mid, 2 * nod);
		updateSmall(anod, poz, val, mid + 1, r, 2 * nod + 1);
		aint[anod][nod] = gcd2(aint[anod][2 * nod], aint[anod][2 * nod + 1]);
	}
}

long long querySmall(int anod, int i, int j, int l, int r, int nod = 1) {
	if(r < i || j < l) return 0;
	if(i <= l && r <= j)
		return aint[anod][nod];
	else if(l < r) {
		int mid = (l + r) / 2;
		return gcd2(querySmall(anod, i, j, l, mid, 2 * nod),
		            querySmall(anod, i, j, mid + 1, r, 2 * nod + 1));
	}
	return 0;
}

void updateBig(int i, int j, long long val, int l, int r, int nod = 1) {
	if(i < l || r < i) return;
	if(l == r)
		updateSmall(nod, j, val, 0, C - 1);
	if(l < r) {
		int mid = (l + r) / 2;
		updateBig(i, j, val, l, mid, 2 * nod);
		updateBig(i, j, val, mid + 1, r, 2 * nod + 1);
		long long x = gcd2(querySmall(2 * nod,     j, j, 0, C - 1),
		                   querySmall(2 * nod + 1, j, j, 0, C - 1));
		updateSmall(nod, j, x, 0, C - 1);
	}
}

long long queryBig(int p, int q, int u, int v, int l, int r, int nod = 1) {
	if(r < p || q < l || p > q) return 0;
	if(p <= l && r <= q)
		return querySmall(nod, u, v, 0, C - 1);
	else if(l < r) {
		int mid = (l + r) / 2;
		return gcd2(queryBig(p, q, u, v, l, mid, 2 * nod),
		            queryBig(p, q, u, v, mid + 1, r, 2 * nod + 1));
	}
	return 0;
}

void init(int _R, int _C) {
	R = _R;
	C = _C;
	aint = new long long*[1+4*_R];
	for(int i = 0; i < 1 + 4 * _R; ++i) {
		aint[i] = new long long[1+4*_C];
		for(int j = 0; j < 1 + 4 * _C; ++j)
			aint[i][j] = 0LL;
	}
}

void update(int P, int Q, long long K) {
	updateBig(P, Q, K, 0, R - 1);
	//updateSmall(P, Q, K, 0, C - 1);
	//aint[P][Q] = K;
}

long long calculate(int P, int Q, int U, int V) {
	//long long rez = 0LL;
	//for(int i = P; i <= U; ++i)
	//	for(int j = Q; j <= V; ++j)
	//		rez = gcd2(aint[i][j], rez);
	//long long rez = 0LL;
	//for(int i = P; i <= U; ++i)
	//	rez = gcd2(rez, querySmall(i, Q, V, 0, C - 1));
	return queryBig(P, U, Q, V, 0, R - 1);
}

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 3 ms 256 KB Output is correct
2 Correct 4 ms 1536 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 3 ms 1536 KB Output is correct
6 Correct 3 ms 1536 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 4 ms 1664 KB Output is correct
10 Correct 4 ms 1536 KB Output is correct
11 Correct 3 ms 1536 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1196 ms 133032 KB Output is correct
5 Correct 778 ms 133276 KB Output is correct
6 Correct 1102 ms 130300 KB Output is correct
7 Correct 1060 ms 129784 KB Output is correct
8 Correct 919 ms 130744 KB Output is correct
9 Correct 1095 ms 130036 KB Output is correct
10 Correct 969 ms 129472 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 1664 KB Output is correct
3 Correct 3 ms 1536 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 1536 KB Output is correct
6 Correct 4 ms 1664 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 1664 KB Output is correct
10 Correct 4 ms 1536 KB Output is correct
11 Correct 4 ms 1536 KB Output is correct
12 Correct 1562 ms 133188 KB Output is correct
13 Correct 2666 ms 130668 KB Output is correct
14 Runtime error 202 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 1664 KB Output is correct
3 Correct 4 ms 1536 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 1536 KB Output is correct
6 Correct 3 ms 1536 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 4 ms 1664 KB Output is correct
10 Correct 4 ms 1664 KB Output is correct
11 Correct 3 ms 1664 KB Output is correct
12 Correct 1175 ms 133124 KB Output is correct
13 Correct 756 ms 133288 KB Output is correct
14 Correct 1044 ms 130060 KB Output is correct
15 Correct 1168 ms 129960 KB Output is correct
16 Correct 853 ms 130780 KB Output is correct
17 Correct 1077 ms 130040 KB Output is correct
18 Correct 936 ms 129660 KB Output is correct
19 Correct 1739 ms 133444 KB Output is correct
20 Correct 2764 ms 130384 KB Output is correct
21 Runtime error 208 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 4 ms 1600 KB Output is correct
3 Correct 4 ms 1536 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 1536 KB Output is correct
6 Correct 4 ms 1536 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 4 ms 1536 KB Output is correct
10 Correct 3 ms 1536 KB Output is correct
11 Correct 5 ms 1536 KB Output is correct
12 Correct 1175 ms 133028 KB Output is correct
13 Correct 750 ms 133496 KB Output is correct
14 Correct 979 ms 130124 KB Output is correct
15 Correct 1125 ms 129836 KB Output is correct
16 Correct 922 ms 130632 KB Output is correct
17 Correct 1029 ms 130064 KB Output is correct
18 Correct 931 ms 129668 KB Output is correct
19 Correct 1457 ms 133324 KB Output is correct
20 Correct 2601 ms 130540 KB Output is correct
21 Runtime error 194 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -