#include "game.h"
using namespace std;
typedef long long llong;
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 n, m;
struct node {
int p[4];
llong sum;
} tree[1000000];
int root = 0;
int newNode() {
static int top = 0;
return top++;
}
void init(int R, int C) {
//n = R; m = C;
root = newNode();
for (int i = 0; i < 4; ++i) tree[root].p[i] = root;
tree[root].sum = 0ll;
}
void updt(int p, int q, int now, int pre, int d, llong k) {
if (d < 0) {
tree[now].sum = k;
return;
}
int j = 1 << d;
int x = ((p & j) == j), y = ((q & j) == j);
for (int i = 0; i < 4; ++i) tree[now].p[i] = tree[pre].p[i];
int nxt = x + y + y;
tree[now].p[nxt] = newNode();
updt(p, q, tree[now].p[nxt], tree[pre].p[nxt], d - 1, k);
tree[now].sum = tree[tree[now].p[0]].sum;
for (int i = 1; i < 4; ++i)
tree[now].sum = gcd2(tree[now].sum, tree[tree[now].p[i]].sum);
return;
}
void update(int P, int Q, llong K) {
int pre = root;
int now = root = newNode();
updt(P, Q, now, pre, 29, K);
return;
}
int p, q, u, v;
llong query(int i, int x, int y, int e) {
if (tree[i].sum == 0ll) return 0ll;
int g = (1 << (e + 1)) - 1;
if (u < x || x + g < p || v < y || y + g < q) return 0ll;
if (p <= x && x + g <= u && q <= y && y + g <= v) return tree[i].sum;
llong ret = 0;
for (int j = 0; j < 4; ++j)
ret = gcd2(ret, query(tree[i].p[j], x + ((j & 1) << e), y + ((j >> 1) << e), e - 1));
return ret;
}
long long calculate(int P, int Q, int U, int V) {
p = P; q = Q; u = U; v = V;
return query(root, 0, 0, 29);
}
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;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 2 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 3 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 4 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 5 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 6 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 7 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 8 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 9 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 10 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 11 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 12 |
Correct |
0 ms |
24552 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 2 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 3 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 4 |
Execution timed out |
13000 ms |
24552 KB |
Execution timed out |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 2 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 3 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 4 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 5 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 6 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 7 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 8 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 9 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 10 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 11 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 12 |
Correct |
12013 ms |
24552 KB |
Output is correct |
| 13 |
Execution timed out |
13000 ms |
24552 KB |
Execution timed out |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 2 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 3 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 4 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 5 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 6 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 7 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 8 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 9 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 10 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 11 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 12 |
Execution timed out |
13000 ms |
24552 KB |
Execution timed out |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 2 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 3 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 4 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 5 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 6 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 7 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 8 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 9 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 10 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 11 |
Correct |
0 ms |
24552 KB |
Output is correct |
| 12 |
Execution timed out |
13000 ms |
24552 KB |
Execution timed out |
| 13 |
Halted |
0 ms |
0 KB |
- |
