# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
553648 |
2022-04-26T12:58:46 Z |
nicholask |
Game (IOI13_game) |
C++14 |
|
1583 ms |
256000 KB |
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
struct smallnode{
smallnode *lc,*rc;
long long val;
smallnode(){
lc=rc=nullptr;
val=0;
}
};
struct bignode{
bignode *lc,*rc;
smallnode *down;
long long val;
bignode(){
lc=rc=nullptr;
down=nullptr;
val=0;
}
};
bignode *root;
long long gcd(long long a,long long b){
while (b) b^=a^=b^=a%=b;
return a;
}
int n,m;
void init(int R,int C){
root=new bignode;
n=R;
m=C;
}
long long queryY(smallnode *id,int tlY,int trY,int lY,int rY){
if (!id||lY>rY) return 0ll;
if (lY<=tlY&&trY<=rY) return id->val;
int tmY=(tlY+trY)/2;
long long lans=(id->lc?queryY(id->lc,tlY,tmY,lY,min(rY,tmY)):0ll);
long long rans=(id->rc?queryY(id->rc,tmY+1,trY,max(lY,tmY+1),rY):0ll);
return gcd(lans,rans);
}
long long queryX(bignode *id,int tlX,int trX,int lX,int rX,int lY,int rY){
if (!id||lX>rX) return 0ll;
if (lX<=tlX&&trX<=rX) return queryY(id->down,1,m,lY,rY);
int tmX=(tlX+trX)/2;
long long lans=(id->lc?queryX(id->lc,tlX,tmX,lX,min(rX,tmX),lY,rY):0ll);
long long rans=(id->rc?queryX(id->rc,tmX+1,trX,max(lX,tmX+1),rX,lY,rY):0ll);
return gcd(lans,rans);
}
void updateY(smallnode *id,int tlY,int trY,int yp,long long Val){
if (!id) return;
if (tlY==trY){
id->val=Val;
return;
}
int tmY=(tlY+trY)/2;
if (yp<=tmY){
if (!id->lc) id->lc=new smallnode;
updateY(id->lc,tlY,tmY,yp,Val);
} else {
if (!id->rc) id->rc=new smallnode;
updateY(id->rc,tmY+1,trY,yp,Val);
}
long long lans=(id->lc?id->lc->val:0ll);
long long rans=(id->rc?id->rc->val:0ll);
id->val=gcd(lans,rans);
}
void updateX(bignode *id,int tlX,int trX,int xp,int yp,long long Val){
if (!id->down) id->down=new smallnode;
if (tlX==trX){
updateY(id->down,1,m,yp,Val);
return;
}
int tmX=(tlX+trX)/2;
if (xp<=tmX){
if (!id->lc) id->lc=new bignode;
updateX(id->lc,tlX,tmX,xp,yp,Val);
} else {
if (!id->rc) id->rc=new bignode;
updateX(id->rc,tmX+1,trX,xp,yp,Val);
}
long long lans=(id->lc?queryY(id->lc->down,1,m,yp,yp):0ll);
long long rans=(id->rc?queryY(id->rc->down,1,m,yp,yp):0ll);
updateY(id->down,1,m,yp,gcd(lans,rans));
}
void update(int P,int Q,long long K){
updateX(root,1,n,P+1,Q+1,K);
}
long long calculate(int P,int Q,int U,int V){
return queryX(root,1,n,P+1,U+1,Q+1,V+1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
296 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
300 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
527 ms |
16960 KB |
Output is correct |
5 |
Correct |
342 ms |
16964 KB |
Output is correct |
6 |
Correct |
442 ms |
14388 KB |
Output is correct |
7 |
Correct |
453 ms |
14228 KB |
Output is correct |
8 |
Correct |
312 ms |
10844 KB |
Output is correct |
9 |
Correct |
460 ms |
14344 KB |
Output is correct |
10 |
Correct |
393 ms |
13872 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
300 KB |
Output is correct |
12 |
Correct |
787 ms |
19916 KB |
Output is correct |
13 |
Correct |
1246 ms |
10088 KB |
Output is correct |
14 |
Correct |
262 ms |
5444 KB |
Output is correct |
15 |
Correct |
1466 ms |
13120 KB |
Output is correct |
16 |
Correct |
233 ms |
22624 KB |
Output is correct |
17 |
Correct |
794 ms |
16116 KB |
Output is correct |
18 |
Correct |
1251 ms |
23096 KB |
Output is correct |
19 |
Correct |
1074 ms |
23180 KB |
Output is correct |
20 |
Correct |
992 ms |
22624 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
483 ms |
16964 KB |
Output is correct |
13 |
Correct |
366 ms |
16916 KB |
Output is correct |
14 |
Correct |
465 ms |
14412 KB |
Output is correct |
15 |
Correct |
432 ms |
14132 KB |
Output is correct |
16 |
Correct |
338 ms |
10824 KB |
Output is correct |
17 |
Correct |
472 ms |
14312 KB |
Output is correct |
18 |
Correct |
398 ms |
13992 KB |
Output is correct |
19 |
Correct |
775 ms |
19884 KB |
Output is correct |
20 |
Correct |
1265 ms |
10184 KB |
Output is correct |
21 |
Correct |
250 ms |
5724 KB |
Output is correct |
22 |
Correct |
1445 ms |
13292 KB |
Output is correct |
23 |
Correct |
212 ms |
22492 KB |
Output is correct |
24 |
Correct |
685 ms |
16300 KB |
Output is correct |
25 |
Correct |
1196 ms |
24024 KB |
Output is correct |
26 |
Correct |
1067 ms |
24076 KB |
Output is correct |
27 |
Correct |
1026 ms |
23368 KB |
Output is correct |
28 |
Correct |
896 ms |
256000 KB |
Output is correct |
29 |
Runtime error |
1583 ms |
256000 KB |
Execution killed with signal 9 |
30 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
514 ms |
16932 KB |
Output is correct |
13 |
Correct |
374 ms |
16852 KB |
Output is correct |
14 |
Correct |
471 ms |
14448 KB |
Output is correct |
15 |
Correct |
545 ms |
14172 KB |
Output is correct |
16 |
Correct |
343 ms |
10836 KB |
Output is correct |
17 |
Correct |
568 ms |
14248 KB |
Output is correct |
18 |
Correct |
512 ms |
13920 KB |
Output is correct |
19 |
Correct |
863 ms |
19924 KB |
Output is correct |
20 |
Correct |
1344 ms |
10048 KB |
Output is correct |
21 |
Correct |
253 ms |
5568 KB |
Output is correct |
22 |
Correct |
1466 ms |
13136 KB |
Output is correct |
23 |
Correct |
213 ms |
22416 KB |
Output is correct |
24 |
Correct |
705 ms |
16416 KB |
Output is correct |
25 |
Correct |
1274 ms |
23940 KB |
Output is correct |
26 |
Correct |
1091 ms |
23972 KB |
Output is correct |
27 |
Correct |
985 ms |
23564 KB |
Output is correct |
28 |
Correct |
928 ms |
256000 KB |
Output is correct |
29 |
Runtime error |
1524 ms |
256000 KB |
Execution killed with signal 9 |
30 |
Halted |
0 ms |
0 KB |
- |