| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 88349 |
2018-12-05T12:06:59 Z |
gs18115 |
Game (IOI13_game) |
C++14 |
|
2 ms |
928 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;
}
int R,C;
struct SY
{
bool flag;
int Y;
SY*l,*r;
LL val;
SY()
{
val=0;
l=r=nullptr;
}
inline void up2(int y,int p)
{
Y=y;
val=p;
return;
}
void update(int L,int R,int y,int p)
{
val=gcd2(val,p);
if(L==R)
return;
int mid=L+R>>1;
if(flag)
{
if(y>mid)
{
if(!r)
{
r=new SY();
r->up2(y,p);
}
else
r->update(mid+1,R,Y,p);
}
else
{
if(!l)
{
l=new SY();
l->up2(Y,p);
}
else
l->update(L,mid,Y,p);
}
flag=false;
}
if(y>mid)
{
if(!r)
{
r=new SY();
r->up2(y,p);
}
else
r->update(mid+1,R,y,p);
}
else
{
if(!l)
{
l=new SY();
l->up2(y,p);
}
else
l->update(L,mid,y,p);
}
return;
}
LL query(int L,int R,int y1,int y2)
{
if(val==-1||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)
{
val->update(Ly,Ry,y,p);
if(Lx==Rx)
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);
}
return;
}
LL query(int Lx,int Rx,int Ly,int Ry,int x1,int x2,int y1,int y2)
{
if(!val||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);
}
}*rt;
void init(int R,int C)
{
::R=R;
::C=C;
rt=new SX();
return;
}
void update(int P,int Q,LL 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:35: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:95: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:122: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:143:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=Lx+Rx>>1;
~~^~~
game.cpp:144:12: warning: variable 'LP' set but not used [-Wunused-but-set-variable]
LL LP,RP;
^~
game.cpp:144:15: warning: variable 'RP' set but not used [-Wunused-but-set-variable]
LL LP,RP;
^~
game.cpp:153:5: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
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 |
624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
