#include "game.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct tree {
ll lb, rb, ub, db, val;
tree *ul, *ur, *bl, *br;
tree () : ul(NULL), ur(NULL), bl(NULL), br(NULL), val(0) {}
inline void initx(ll l, ll r, ll u, ll d){
lb = l, rb = r, ub = u, db = d;
}
inline void extend(int num){
ll mid1 = (lb+rb)>>1;
ll mid2 = (ub+db)>>1;
if(num == 0){
if(!ul){
ul = new tree();
ul->initx(lb,mid1,ub,mid2);
}
return;
}
if(num == 1){
if(!ur){
ur = new tree();
ur->initx(mid1+(lb == rb ? 0 : 1),rb,ub,mid2);
}
return;
}
if(num == 2){
if(!bl){
bl = new tree();
bl->initx(lb,mid1,mid2+(ub == db ? 0 : 1),db);
}
return;
}
if(!br){
br = new tree();
br->initx(mid1+(lb == rb ? 0 : 1),rb,mid2+(ub == db ? 0 : 1),db);
}
}
ll getGCD(ll l, ll r, ll u, ll d){
if(r < lb || rb < l || d < ub || db < u){
return 0;
}
if(l <= lb && rb <= r && u <= ub && db <= d){
return val;
}
ll mid11 = (lb+rb)>>1, mid22 = (db+ub)>>1;
ll ret = 0;
if(l <= mid11 && u <= mid22){extend(0);ret = gcd2(ret,ul->getGCD(l,r,u,d));}
if(mid11 < r && u <= mid22){extend(1);ret = gcd2(ret,ur->getGCD(l,r,u,d));}
if(l <= mid11 && mid22 < d){extend(2);ret = gcd2(ret,bl->getGCD(l,r,u,d));}
if(mid11 < r && mid22 < d){extend(3);ret = gcd2(ret,br->getGCD(l,r,u,d));}
return ret;
}
void chan(ll p1, ll p2, ll ne){
if(lb == rb && ub == db){
val = ne;
return;
}
ll ret = 0;
ll mid11 = (lb+rb)>>1, mid22 = (db+ub)>>1;
if(p1 <= mid11 && p2 <= mid22){extend(0);ul->chan(p1,p2,ne);}
else if(p2 <= mid22){extend(1);ur->chan(p1,p2,ne);}
else if(p1 <= mid11){extend(2);bl->chan(p1,p2,ne);}
else {extend(3);br->chan(p1,p2,ne);}
if(ul)ret = gcd2(ret,ul->val);
if(ur)ret = gcd2(ret,ur->val);
if(bl)ret = gcd2(ret,bl->val);
if(br)ret = gcd2(ret,br->val);
val = ret;
return;
}
};
tree *root = new tree();
void init(int R, int C) {
root->initx(0,C+4,0,R+4);
}
void update(int P, int Q, long long K) {
root->chan(Q,P,K);
}
long long calculate(int P, int Q, int U, int V) {
return root->getGCD(Q,V,P,U);
}
Compilation message
game.cpp: In constructor 'tree::tree()':
game.cpp:20:23: warning: 'tree::br' will be initialized after [-Wreorder]
20 | tree *ul, *ur, *bl, *br;
| ^~
game.cpp:19:21: warning: 'll tree::val' [-Wreorder]
19 | ll lb, rb, ub, db, val;
| ^~~
game.cpp:22:2: warning: when initialized here [-Wreorder]
22 | tree () : ul(NULL), ur(NULL), bl(NULL), br(NULL), val(0) {}
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
2 ms |
896 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
896 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
768 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Runtime error |
257 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
2 ms |
896 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
896 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
768 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Execution timed out |
13048 ms |
18080 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
896 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
896 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
768 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Runtime error |
258 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
2 ms |
928 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
896 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
768 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Runtime error |
260 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
13 |
Halted |
0 ms |
0 KB |
- |