| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 88495 |
2018-12-06T07:29:00 Z |
gs18115 |
Game (IOI13_game) |
C++14 |
|
790 ms |
9920 KB |
#include "game.h"
#include<cassert>
#include<iostream>
using namespace std;
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,LL p)
{
Y=y;
val=p;
return;
}
void update(int L,int R,int y,LL 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);
}
flag=false;
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;
}
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,LL p)
{
if(L==R)
{
val=P->val;
Y=P->Y;
return;
}
int mid=L+R>>1;
val=P->val;
Y=P->Y;
flag=P->flag;
if(flag)
return;
if(y>mid)
{
if(!P->r)
assert(false);
else if(!r)
{
r=new SY();
r->update(y,p);
}
else
r->update(P->r,mid+1,R,y,p);
}
else
{
if(!P->l)
assert(false);
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,LL p)
{
if(L==R)
{
val=gcd2(Lp->val,Rp->val);
flag=false;
return;
}
int mid=L+R>>1;
if(flag)
{
flag=false;
if(Y>mid)
{
r=new SY();
r->update(Y,val);
}
else
{
l=new SY();
l->update(Y,val);
}
}
if(Lp->flag)
{
Lp->flag=false;
if(Lp->Y>mid)
{
Lp->r=new SY();
Lp->r->update(Lp->Y,Lp->val);
}
else
{
Lp->l=new SY();
Lp->l->update(Lp->Y,Lp->val);
}
}
if(Rp->flag)
{
Rp->flag=false;
if(Rp->Y>mid)
{
Rp->r=new SY();
Rp->r->update(Rp->Y,Rp->val);
}
else
{
Rp->l=new SY();
Rp->l->update(Rp->Y,Rp->val);
}
}
val=gcd2(Lp->val,Rp->val);
if(y>mid)
{
if(!Lp->r&&!Rp->r)
assert(false);
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)
assert(false);
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);
}
};
int R,C;
struct SX
{
SX*l,*r;
SY*val;
SX()
{
val=new SY();
l=r=nullptr;
}
void update(int L,int R,int x,int y,LL p)
{
if(L==R)
{
val->update(0,C-1,y,p);
return;
}
int mid=L+R>>1;
if(x>mid)
{
if(!r)
r=new SX();
r->update(mid+1,R,x,y,p);
}
else
{
if(!l)
l=new SX();
l->update(L,mid,x,y,p);
}
if(!r)
val->update(l->val,0,C-1,y,p);
else if(!l)
val->update(r->val,0,C-1,y,p);
else
val->update(l->val,r->val,0,C-1,y,p);
return;
}
LL query(int L,int R,int x1,int x2,int y1,int y2)
{
if(L>x2||R<x1)
return 0;
if(L>=x1&&R<=x2)
return val->query(0,C-1,y1,y2);
int mid=L+R>>1;
LL LP,RP;
if(!l)
LP=0;
else
LP=l->query(L,mid,x1,x2,y1,y2);
if(!r)
RP=0;
else
RP=r->query(mid+1,R,x1,x2,y1,y2);
return gcd2(LP,RP);
}
}*rt;
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,P,Q,K);
return;
}
LL calculate(int P,int Q,int U,int V)
{
return rt->query(0,R-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, LL)':
game.cpp:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=L+R>>1;
~^~
game.cpp: In member function 'void SY::update(SY*, int, int, int, LL)':
game.cpp:131: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, LL)':
game.cpp:171: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:262:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=L+R>>1;
~^~
game.cpp: In member function 'void SX::update(int, int, int, int, LL)':
game.cpp:292:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=L+R>>1;
~^~
game.cpp: In member function 'LL SX::query(int, int, int, int, int, int)':
game.cpp:319:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=L+R>>1;
~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
500 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
500 KB |
Output is correct |
| 2 |
Correct |
2 ms |
524 KB |
Output is correct |
| 3 |
Correct |
2 ms |
524 KB |
Output is correct |
| 4 |
Incorrect |
790 ms |
9920 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9920 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
9920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9920 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
9920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9920 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
9920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
