| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 88372 |
2018-12-05T14:14:31 Z |
gs18115 |
Game (IOI13_game) |
C++14 |
|
2 ms |
424 KB |
#include "game.h"
typedef long long LL;
LL gcd2(LL X, LL Y) {
LL tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct SY
{
bool flag;
int Y;
SY*l,*r;
LL val;
SY()
{
flag=true;
val=0;
l=r=nullptr;
}
inline void update(int y,int p)
{
Y=y;
val=p;
return;
}
void update(int L,int R,int y,int p)
{
if(L==R)
{
val=p;
return;
}
int mid=L+R>>1;
if(flag)
{
if(Y==y)
{
val=p;
return;
}
if(Y>mid)
{
r=new SY();
r->update(Y,val);
}
else
{
l=new SY();
l->update(Y,val);
}
if(y>mid)
{
if(!r)
{
r=new SY();
r->update(y,p);
}
else
r->update(mid+1,R,y,p);
}
else
{
if(!l)
{
l=new SY();
l->update(y,p);
}
else
l->update(L,mid,y,p);
}
flag=false;
LL LP,RP;
if(!l)
LP=0;
else
LP=l->val;
if(!r)
RP=0;
else
RP=r->val;
val=gcd2(LP,RP);
return;
}
if(y>mid)
{
if(!r)
{
r=new SY();
r->update(y,p);
}
else
r->update(mid+1,R,y,p);
}
else
{
if(!l)
{
l=new SY();
l->update(y,p);
}
else
l->update(L,mid,y,p);
}
LL LP,RP;
if(!l)
LP=0;
else
LP=l->val;
if(!r)
RP=0;
else
RP=r->val;
val=gcd2(LP,RP);
return;
}
void update(SY*P,int L,int R,int y,int p)
{
val=P->val;
flag=P->flag;
Y=P->Y;
if(L==R)
return;
int mid=L+R>>1;
if(y>mid)
{
if(!P->r)
return;
else if(!r)
{
r=new SY();
r->update(y,p);
}
else
r->update(P->r,mid+1,R,y,p);
}
else
{
if(!P->l)
return;
else if(!l)
{
l=new SY();
l->update(y,p);
}
else
l->update(P->l,L,mid,y,p);
}
return;
}
void update(SY*Lp,SY*Rp,int L,int R,int y,int p)
{
val=gcd2(Lp->val,Rp->val);
flag=false;
if(L==R)
return;
int mid=L+R>>1;
if(y>mid)
{
if(!Lp->r&&!Rp->r)
return;
else if(!r)
{
r=new SY();
r->update(y,p);
}
else if(!Lp->r)
r->update(Rp->r,mid+1,R,y,p);
else if(!Rp->r)
r->update(Lp->r,mid+1,R,y,p);
else
r->update(Lp->r,Rp->r,mid+1,R,y,p);
}
else
{
if(!Lp->l&&!Rp->l)
return;
else if(!l)
{
l=new SY();
l->update(y,p);
}
else if(!Lp->l)
l->update(Rp->l,L,mid,y,p);
else if(!Rp->l)
l->update(Lp->l,L,mid,y,p);
else
l->update(Lp->l,Rp->l,L,mid,y,p);
}
return;
}
LL query(int L,int R,int y1,int y2)
{
if(L>y2||R<y1)
return 0;
if(L>=y1&&R<=y2)
return val;
if(flag)
{
if(y1<=Y&&Y<=y2)
return val;
else
return 0;
}
int mid=L+R>>1;
LL LP,RP;
if(!l)
LP=0;
else
LP=l->query(L,mid,y1,y2);
if(!r)
RP=0;
else
RP=r->query(mid+1,R,y1,y2);
return gcd2(LP,RP);
}
};
struct SX
{
SX*l,*r;
SY*val;
SX()
{
val=new SY();
l=r=nullptr;
}
void update(int Lx,int Rx,int Ly,int Ry,int x,int y,int p)
{
if(Lx==Rx)
{
val->update(Ly,Ry,y,p);
return;
}
int mid=Lx+Rx>>1;
if(x>mid)
{
if(!r)
r=new SX();
r->update(mid+1,Rx,Ly,Ry,x,y,p);
}
else
{
if(!l)
l=new SX();
l->update(Lx,mid,Ly,Ry,x,y,p);
}
if(!r)
val->update(l->val,Ly,Ry,y,p);
else if(!l)
val->update(r->val,Ly,Ry,y,p);
else
val->update(l->val,r->val,Ly,Ry,y,p);
return;
}
LL query(int Lx,int Rx,int Ly,int Ry,int x1,int x2,int y1,int y2)
{
if(Lx>x2||Rx<x1)
return 0;
if(Lx>=x1&&Rx<=x2)
return val->query(Ly,Ry,y1,y2);
int mid=Lx+Rx>>1;
LL LP,RP;
if(!l)
LP=0;
else
LP=l->query(Lx,mid,Ly,Ry,x1,x2,y1,y2);
if(!r)
RP=0;
else
RP=r->query(mid+1,Rx,Ly,Ry,x1,x2,y1,y2);
return gcd2(LP,RP);
}
}*rt;
int R,C;
void init(int R,int C)
{
::R=R;
::C=C;
rt=new SX();
return;
}
void update(int P,int Q,long long K)
{
rt->update(0,R-1,0,C-1,P,Q,K);
return;
}
LL calculate(int P,int Q,int U,int V)
{
return rt->query(0,R-1,0,C-1,P,U,Q,V);
}
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;
^~~
game.cpp: In member function 'void SY::update(int, int, int, int)':
game.cpp:37:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=L+R>>1;
~^~
game.cpp: In member function 'void SY::update(SY*, int, int, int, int)':
game.cpp:127:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=L+R>>1;
~^~
game.cpp: In member function 'void SY::update(SY*, SY*, int, int, int, int)':
game.cpp:160:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=L+R>>1;
~^~
game.cpp: In member function 'LL SY::query(int, int, int, int)':
game.cpp:208:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=L+R>>1;
~^~
game.cpp: In member function 'void SX::update(int, int, int, int, int, int, int)':
game.cpp:237:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=Lx+Rx>>1;
~~^~~
game.cpp: In member function 'LL SX::query(int, int, int, int, int, int, int, int)':
game.cpp:264:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=Lx+Rx>>1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
