#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;
}
struct nodeY {
int x, y;
nodeY *l, *r;
llong sum;
};
struct nodeX {
nodeX *l, *r;
nodeY *t;
} treeX[31 * 22000 + 1];
nodeX * root;
nodeY * makeY() {
//static int top = 0;
nodeY * ret = new nodeY;
ret->l = 0;
ret->r = 0;
ret->sum = 0;
return ret;
}
int n, m;
nodeX * makeX() {
static int top = 0;
treeX[top].t = makeY();
treeX[top].t->y = m - 1;
return treeX + (top++);
}
void init(int r, int c) {
n = r; m = c;
root = makeX();
}
int p, q, u, v, k, uk;
void updtY(nodeY * now) {
if (now->x == now->y) {
now->sum = uk;
return;
}
int md = (now->x + now->y) / 2;
nodeY *& nxt = q <= md ? now->l : now->r;
if (nxt == 0) {
nxt = makeY();
nxt->x = nxt->y = q;
nxt->sum = uk;
}
else if (nxt->x <= q && q <= nxt->y) {
updtY(nxt);
}
else {
nodeY * nw = makeY();
nw->x = now->x;
nw->y = now->y;
do {
if (q <= md) nw->y = md;
else nw->x = md + 1;
md = (nw->x + nw->y) / 2;
} while ((q <= md) == (nxt->x <= md));
if (q <= md) nw->r = nxt;
else nw->l = nxt;
nxt = nw;
updtY(nw);
}
now->sum = gcd2(now->l ? now->l->sum : 0ll, now->r ? now->r->sum : 0ll);
}
llong queryY(nodeY * now) {
if (now == 0) return 0ll;
if (v < now->x || now->y < q) return 0ll;
if (q <= now->x && now->y <= v) return now->sum;
int md = (now->x + now->y) / 2;
return gcd2(queryY(now->l), queryY(now->r));
}
void updtX(nodeX * now, int x, int y) {
if (x == y) {
uk = k;
updtY(now->t);
return;
}
int md = (x + y) / 2;
if (p <= md) {
if (now->l == 0) now->l = makeX();
updtX(now->l, x, md);
}
else {
if (now->r == 0) now->r = makeX();
updtX(now->r, md + 1, y);
}
uk = gcd2(now->l ? queryY(now->l->t) : 0ll, now->r ? queryY(now->r->t) : 0ll);
updtY(now->t);
}
llong queryX(nodeX * now, int x, int y) {
if (now == 0) return 0ll;
if (u < x || y < p) return 0ll;
if (p <= x && y <= u) return queryY(now->t);
int md = (x + y) / 2;
return gcd2(queryX(now->l, x, md), queryX(now->r, md + 1, y));
}
void update(int P, int Q, llong K) {
p = u = P;
q = v = Q;
k = K;
updtX(root, 0, n - 1);
}
long long calculate(int P, int Q, int U, int V) {
p = P; q = Q; u = U; v = V;
return queryX(root, 0, n - 1);
}
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;
^
game.cpp: In function 'llong queryY(nodeY*)':
game.cpp:88:6: warning: unused variable 'md' [-Wunused-variable]
int md = (now->x + now->y) / 2;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
17156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
17156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
17156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
17156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
17156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
