| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 308066 |
2020-09-30T02:35:30 Z |
daniel920712 |
Game (IOI13_game) |
C++14 |
|
0 ms |
0 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);
}
//if(y==76) printf("%lld %lld %lld %lld\n",y,Node[here].l,Node[here].r,Node[here].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)
{
//printf("%lld %lld %lld %lld %lld\n",x1,y1,x2,y2,here);
if(here==-1) return 0;
if(Node[here].nxt==-2)
{
if(Node[here].l==x2&&Node[here].r==y2)
{
//printf("%lld %lld %lld\n",x2,y2,Node[here].con);
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,x2,(Node[here].l+Node[here].r)/2,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)
{
long long ans=0,i;
//printf("aaa\n");
ans=Find(P,U,Q,V);
/*for(i=P;i<=U;i++)
{
ans=gcd2(ans,Find(i,i,Q,V,0));
//if(P==60) printf("%lld %lld\n",i,Find(i,i,Q,V,0));
}*/
//printf("cc %lld\n",ans);
return ans;
}
Compilation message
game.cpp: In function 'long long int calculate(int, int, int, int)':
game.cpp:180:21: error: too few arguments to function 'long long int Find(long long int, long long int, long long int, long long int, long long int)'
180 | ans=Find(P,U,Q,V);
| ^
game.cpp:148:11: note: declared here
148 | long long Find(long long x1,long long y1,long long x2,long long y2,long long here)
| ^~~~
game.cpp:178:21: warning: unused variable 'i' [-Wunused-variable]
178 | long long ans=0,i;
| ^
