#include "game.h"
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = ((int)1<<30)-1;
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 {
long long val;
node *lup, *ldown, *rup, *rdown;
node(long long q = 0) {
val = q;
lup = ldown = rup= rdown=NULL;
}
};
node *root;
node* get_node() {
static node T[5000 * 1000];
static int counter = 0;
return &T[counter++];
}
inline long long get_(node *t) {
return t ? t->val : 0ll;
}
inline bool in_(int llx, int lly, int rrx, int rry, int nx, int ny) {
return (llx <= nx&&lly <= ny&&rrx >= nx&&rry >= ny);
}
bool in_rect(int llx, int lly, int rrx, int rry, int nlx, int nly, int nrx, int nry) {
return (nrx < llx || nry < lly || rrx < nlx || rry < nly)? 0:1;
}
void init(int R, int C) {
/* ... */
}
void updatequard(int x, int y, long long val, node *&t, int nlx, int nly, int nrx, int nry) {
if (!t)t = get_node();
// cout << x << " " << y << endl;
// cout << nlx << " " << nly << " " << nrx << " " << nry << endl;
// cout << "level" << endl;
if (nlx == nrx&&nry == nly) {
t->val = val;
return;
}
int mx = (nlx + nrx) / 2;
int my = (nly + nry) / 2;
// ldown
if (in_(nlx, nly, mx, my, x, y))updatequard(x, y, val, t->ldown, nlx, nly, mx, my);
// lup
else if (in_(mx+1, nly, nrx, my, x, y))updatequard(x, y, val, t->lup, mx+1, nly, nrx, my);
// rdown
else if (in_(nlx, my+1, mx,nry, x, y))updatequard(x, y, val, t->rdown, nlx, my+1, mx, nry);
//rup
else updatequard(x, y, val, t->rup, mx+1, my+1, nrx, nry);
t->val = gcd2(
gcd2(get_(t->ldown), get_(t->lup)),
gcd2(get_(t->rdown), get_(t->rup))
);
}
void update(int P, int Q, long long K) {
/* ... */
updatequard(P, Q, K, root, 0, 0, N, N);
// cout << "hi" << endl;
}
long long get(int llx, int lly, int rrx, int rry, node *t, int nlx, int nly, int nrx, int nry) {
if (!t)return 0ll;
if (in_(llx, lly, rrx, rry, nlx, nly) && in_(llx, lly, rrx, rry, nrx, nry))return t->val;
// cout << llx << " " << lly << " " << rrx << " " << rry << " " << nlx << " " << nly << " " << nrx << " " << nry << endl;
int mx = (nlx + nrx) / 2;
int my = (nly + nry) / 2;
long long cur = 0;
// ldown
if (in_rect(llx, lly, rrx, rry, nlx,nly,mx, my))cur = gcd2(cur, get(llx, lly, rrx, rry, t->ldown, nlx, nly, mx, my));
// lup
if (in_rect(llx, lly, rrx, rry, mx + 1, nly, nrx, my))cur = gcd2(cur, get(llx, lly, rrx, rry, t->lup, mx+1, nly, nrx, my));
// rdown
if (in_rect(llx, lly, rrx, rry, nlx, my + 1, mx, nry))cur = gcd2(cur, get(llx, lly, rrx, rry, t->rdown, nlx, my+1, mx, nry));
//rup
if (in_rect(llx, lly, rrx, rry, mx + 1, my + 1, nrx, nry))cur = gcd2(cur, get(llx, lly, rrx, rry, t->ldown, mx+1,my+1, nrx,nry));
return cur;
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
return get(P,Q,U,V,root,0,0,N,N);
}
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 |
16 ms |
197332 KB |
Output is correct |
2 |
Incorrect |
39 ms |
197332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
197332 KB |
Output is correct |
2 |
Incorrect |
26 ms |
197332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
197332 KB |
Output is correct |
2 |
Incorrect |
29 ms |
197332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
197332 KB |
Output is correct |
2 |
Incorrect |
26 ms |
197332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
197332 KB |
Output is correct |
2 |
Incorrect |
16 ms |
197332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |