#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;
}
struct Node{
int x1, x2, y1, y2;
long long gcd = 0;
Node* dx[2] = {NULL};
Node* dy[2] = {NULL};
Node(int _x1, int _y1, int _x2, int _y2){
x1 = _x1;
y1 = _y1;
x2 = _x2;
y2 = _y2;
}
void create(){
if(dx[0] != NULL || dy[0] != NULL) return;
if(x1 != x2){
int m = (x1 + x2) >> 1;
dx[0] = new Node(x1, y1, m, y2);
dx[1] = new Node(m + 1, y1, x2, y2);
}
if(y1 != y2){
int m = (y1 + y2) >> 1;
dy[0] = new Node(x1, y1, x2, m);
dy[1] = new Node(x1, m + 1, x2, y2);
}
}
void update(int x, int y, long long val){
if(x1 == x2 && y1 == y2){
gcd = val;
return;
}
create();
if(x1 != x2){
int m = (x1 + x2) >> 1;
dx[x > m] -> update(x, y, val);
gcd = gcd2(dx[0] -> gcd, dx[1] -> gcd);
}
if(y1 != y2){
int m = (y1 + y2) >> 1;
dy[y > m] -> update(x, y, val);
gcd = gcd2(dy[0] -> gcd, dy[1] -> gcd);
}
}
long long query(int qx1, int qy1, int qx2, int qy2){
if(gcd == 0) return 0;
if(x1 == x2 && y1 == y2) return gcd;
if(qx1 == x1 && qx2 == x2 && qy1 == y1 && qy2 == y2) return gcd;
int mx = (x1 + x2) >> 1;
int my = (y1 + y2) >> 1;
if(mx >= qx2){
return dx[0] -> query(qx1, qy1, qx2, qy2);
} else if(mx < qx1){
return dx[1] -> query(qx1, qy1, qx2, qy2);
}
if(my >= qy2){
return dy[0] -> query(qx1, qy1, qx2, qy2);
} else if(my < qy1){
return dy[1] -> query(qx1, qy1, qx2, qy2);
}
if(dx[0] != NULL)
return gcd2(dx[0] -> query(qx1, qy1, mx, qy2), dx[1] -> query(mx + 1, qy1, qx2, qy2));
return gcd2(dy[0] -> query(qx1, qy1, qx2, my), dy[1] -> query(qx1, my + 1, qx2, qy2));
}
} *root;
void init(int R, int C) {
root = new Node(0, 0, R - 1, C - 1);
}
void update(int P, int Q, long long K) {
root -> update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
return root -> query(P, Q, U, V);
}
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 |
2 ms |
256 KB |
Output is correct |
2 |
Runtime error |
266 ms |
232568 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Runtime error |
279 ms |
232444 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Runtime error |
286 ms |
232600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Runtime error |
275 ms |
232520 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |