| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 390253 |
2021-04-15T16:12:54 Z |
rainboy |
Game (IOI13_game) |
C |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
