| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 93861 |
2019-01-12T13:43:59 Z |
alexpetrescu |
Game (IOI13_game) |
C++14 |
|
13000 ms |
150892 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*[nrcol];
for (int j = 0; j < nrcol; j++) {
rmq[i][j] = new long long[lg2[nrcol] + 1];
for (int b = 0; b <= lg2[nrcol]; b++)
rmq[i][j][b] = 0;
}
}
}
void update(int P, int Q, long long K) {
rmq[P][Q][0] = K;
for (int j = Q; j < nrcol; j++)
for (int b = 1; (1 << b) <= j + 1; b++)
rmq[P][j][b] = gcd2(rmq[P][j][b - 1], rmq[P][j - (1 << (b - 1))][b - 1]);
}
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][V][b], rmq[i][Q][b]));
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 |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Execution timed out |
13080 ms |
150892 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
252 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
2 ms |
252 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1020 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 12 |
Execution timed out |
13073 ms |
103956 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 |
1016 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1020 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 12 |
Execution timed out |
13079 ms |
150796 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 |
1020 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 12 |
Execution timed out |
13041 ms |
150868 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
