| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 308059 |
2020-09-30T02:10:52 Z |
daniel920712 |
Game (IOI13_game) |
C++14 |
|
1 ms |
512 KB |
#include "game.h"
#include <stdio.h>
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 A
{
long long l,r;
long long nxl,nxr,nxt;
long long con;
}Node[2000005];
long long N,M,now=1;
void New(long long l,long long r,long long here,long long t)
{
Node[here].l=l;
Node[here].r=r;
Node[here].nxt=t;
Node[here].nxl=-1;
Node[here].nxr=-1;
Node[here].con=0;
}
void init(int R, int C)
{
N=R;
M=C;
New(0,N-1,0,-1);
}
void Merge(long long here,long long l,long long r,long long what)
{
int ll,rr;
if(what==Node[here].l&&what==Node[here].r)
{
Node[here].con=0;
if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con);
if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con);
//printf("%d %d %d\n",Node[here].l,Node[here].r,Node[here].con);
return;
}
if(what<=(Node[here].l+Node[here].r)/2)
{
if(Node[here].nxl==-1)
{
Node[here].nxl=now++;
New(Node[here].l,(Node[here].l+Node[here].r)/2,Node[here].nxl,-2);
}
if(l!=-1) ll=Node[l].nxl;
if(r!=-1) rr=Node[r].nxl;
Merge(Node[here].nxl,ll,rr,what);
Node[here].con=0;
if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con);
if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con);
}
else
{
if(Node[here].nxr==-1)
{
Node[here].nxr=now++;
New((Node[here].l+Node[here].r)/2+1,Node[here].r,Node[here].nxr,-2);
}
if(l!=-1) ll=Node[l].nxr;
if(r!=-1) rr=Node[r].nxr;
Merge(Node[here].nxr,ll,rr,what);
Node[here].con=0;
if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con);
if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con);
}
//printf("%d %d %d\n",Node[here].l,Node[here].r,Node[here].con);
}
void cha(long long x,long long y,long long con,long long here)
{
if(Node[here].nxt==-2)
{
if(y==Node[here].l&&y==Node[here].r)
{
Node[here].con=con;
return;
}
if(y<=(Node[here].l+Node[here].r)/2)
{
if(Node[here].nxl==-1)
{
Node[here].nxl=now++;
New(Node[here].l,(Node[here].l+Node[here].r)/2,Node[here].nxl,-2);
}
cha(x,y,con,Node[here].nxl);
Node[here].con=Node[Node[here].nxl].con;
if(Node[here].nxr!=-1) Node[here].con=gcd2(Node[here].con,Node[Node[here].nxr].con);
}
else
{
if(Node[here].nxr==-1)
{
Node[here].nxr=now++;
New((Node[here].l+Node[here].r)/2+1,Node[here].r,Node[here].nxr,-2);
}
cha(x,y,con,Node[here].nxr);
Node[here].con=Node[Node[here].nxr].con;
if(Node[here].nxl!=-1) Node[here].con=gcd2(Node[here].con,Node[Node[here].nxl].con);
}
}
else
{
if(x==Node[here].l&&x==Node[here].r)
{
if(Node[here].nxt==-1)
{
Node[here].nxt=now++;
New(0,M-1,Node[here].nxt,-2);
}
cha(x,y,con,Node[here].nxt);
return;
}
if(x<=(Node[here].l+Node[here].r)/2)
{
if(Node[here].nxl==-1)
{
Node[here].nxl=now++;
New(Node[here].l,(Node[here].l+Node[here].r)/2,Node[here].nxl,-1);
}
cha(x,y,con,Node[here].nxl);
}
else
{
if(Node[here].nxr==-1)
{
Node[here].nxr=now++;
New((Node[here].l+Node[here].r)/2+1,Node[here].r,Node[here].nxr,-1);
}
cha(x,y,con,Node[here].nxr);
}
if(Node[here].nxt==-1)
{
Node[here].nxt=now++;
New(0,M-1,Node[here].nxt,-2);
}
//printf("aa %d %d\n",Node[here].l,Node[here].r);
Merge(Node[here].nxt,Node[Node[here].nxl].nxt,Node[Node[here].nxr].nxt,y);
}
}
long long Find(long long x1,long long y1,long long x2,long long y2,long long here)
{
if(here==-1) return 0;
if(Node[here].nxt==-2)
{
if(Node[here].l==x2&&Node[here].r==y2) return Node[here].con;
if(y2<=(Node[here].l+Node[here].r)/2) return Find(x1,y1,x2,y2,Node[here].nxl);
if(x2>(Node[here].l+Node[here].r)/2) return Find(x1,y1,x2,y2,Node[here].nxr);
return gcd2(Find(x1,y1,(Node[here].l+Node[here].r)/2,y2,Node[here].nxl),Find(x1,y1,(Node[here].l+Node[here].r)/2+1,y2,Node[here].nxr));
}
else
{
if(Node[here].l==x1&&Node[here].r==y1) return Find(x1,y1,x2,y2,Node[here].nxt);
if(y1<=(Node[here].l+Node[here].r)/2) return Find(x1,y1,x2,y2,Node[here].nxl);
if(x1>(Node[here].l+Node[here].r)/2) return Find(x1,y1,x2,y2,Node[here].nxr);
return gcd2(Find(x1,(Node[here].l+Node[here].r)/2,x2,y2,Node[here].nxl),Find((Node[here].l+Node[here].r)/2+1,y1,x2,y2,Node[here].nxr));
}
}
void update(int P, int Q, long long K)
{
cha(P,Q,K,0);
}
long long calculate(int P, int Q, int U, int V) {
return Find(P,U,Q,V,0);
}
Compilation message
game.cpp: In function 'void Merge(long long int, long long int, long long int, long long int)':
game.cpp:36:9: warning: 'll' may be used uninitialized in this function [-Wmaybe-uninitialized]
36 | int ll,rr;
| ^~
game.cpp:54:14: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
54 | Merge(Node[here].nxl,ll,rr,what);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
