| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 93863 |
2019-01-12T13:53:39 Z |
alexpetrescu |
Game (IOI13_game) |
C++14 |
|
13000 ms |
135812 KB |
#include "game.h"
#include <cstring>
#include <algorithm>
long long ***rmq;
int nrlin, nrcol, lg2[100001];
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 init(int R, int C) {
nrlin = R;
nrcol = C;
int n = std::max(nrlin, nrcol);
for (int i = 2; i <= n; i++)
if ((1 << (lg2[i - 1] + 1)) == i)
lg2[i] = lg2[i - 1] + 1;
else
lg2[i] = lg2[i - 1];
rmq = new long long**[nrlin];
for (int i = 0; i < nrlin; i++) {
rmq[i] = new long long*[lg2[nrcol] + 1];
for (int j = 0; j <= lg2[nrcol]; j++) {
rmq[i][j] = new long long[nrcol];
for (int b = 0; b < nrcol; b++)
rmq[i][j][b] = 0;
}
}
}
void update(int P, int Q, long long K) {
rmq[P][0][Q] = K;
for (int b = 1; b <= lg2[nrcol]; b++) {
int u = 1 << (b - 1);
for (int j = (1 << b) - 1; j < nrcol; j++)
rmq[P][b][j] = gcd2(rmq[P][b - 1][j], rmq[P][b - 1][j - u]);
}
}
long long calculate(int P, int Q, int U, int V) {
int b = lg2[V - Q + 1];
Q += (1 << b) - 1;
long long ans = 0;
for (int i = P; i <= U; i++)
ans = gcd2(ans, gcd2(rmq[i][b][V], rmq[i][b][Q]));
return ans;
}
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;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
888 KB |
Output is correct |
| 3 |
Correct |
3 ms |
888 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
888 KB |
Output is correct |
| 6 |
Correct |
3 ms |
888 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
888 KB |
Output is correct |
| 10 |
Correct |
3 ms |
888 KB |
Output is correct |
| 11 |
Correct |
3 ms |
888 KB |
Output is correct |
| 12 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Execution timed out |
13010 ms |
135812 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
888 KB |
Output is correct |
| 3 |
Correct |
2 ms |
888 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
888 KB |
Output is correct |
| 6 |
Correct |
2 ms |
888 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
888 KB |
Output is correct |
| 10 |
Correct |
2 ms |
888 KB |
Output is correct |
| 11 |
Correct |
2 ms |
888 KB |
Output is correct |
| 12 |
Execution timed out |
13023 ms |
82612 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
888 KB |
Output is correct |
| 3 |
Correct |
2 ms |
892 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
888 KB |
Output is correct |
| 6 |
Correct |
2 ms |
888 KB |
Output is correct |
| 7 |
Correct |
2 ms |
380 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
892 KB |
Output is correct |
| 10 |
Correct |
2 ms |
888 KB |
Output is correct |
| 11 |
Correct |
2 ms |
888 KB |
Output is correct |
| 12 |
Execution timed out |
13047 ms |
135700 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
888 KB |
Output is correct |
| 3 |
Correct |
2 ms |
888 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
888 KB |
Output is correct |
| 6 |
Correct |
2 ms |
888 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
888 KB |
Output is correct |
| 10 |
Correct |
2 ms |
888 KB |
Output is correct |
| 11 |
Correct |
3 ms |
888 KB |
Output is correct |
| 12 |
Execution timed out |
13070 ms |
135680 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
