| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 18949 |
2016-02-16T17:01:14 Z |
ggoh |
Game (IOI13_game) |
C++ |
|
0 ms |
0 KB |
#include<cstdio>
#include<algorithm>
#include<vector>
int a,b,X,t;
struct A{
int s,e,left,right,ynum;
long long val;
};
std::vector<A>xTree,yTree;
long long gcd2(long long xx,long long yy){
if(yy==0)return xx;
return gcd2(yy,xx%yy);
}
void yup(int num,int xco,int yco,long long v)
{
int s1=yTree[num].s,e1=yTree[num].e;
if(s1==e1){
yTree[num].val=v;
return ;
}
if((s1+e1)/2>=yco)
{
if(yTree[num].left==-1)
{
yTree[num].left=yTree.size();
yTree.push_back({s1,(s1+e1)/2,-1,-1,-1,0});
}
yup(yTree[num].left,xco,yco,v);
}
else
{
if(yTree[num].right==-1)
{
yTree[num].right=yTree.size();
yTree.push_back({(s1+e1)/2+1,e1,-1,-1,-1,0});
}
yup(yTree[num].right,xco,yco,v);
}
long long l=0,r=0;
if(yTree[num].left>=0)l=yTree[yTree[num].left].val;
if(yTree[num].right>=0)r=yTree[yTree[num].right].val;
yTree[num].val=gcd2(l,r);
}
void xup(int num,int xco,int yco,long long v)
{
if(xTree[num].ynum==-1)
{
xTree[num].ynum=yTree.size();
yTree.push_back({0,X,-1,-1,-1,0});
}
yup(xTree[num].ynum,xco,yco,v);
if(xTree[num].s==xTree[num].e)return ;
int s1=xTree[num].s,e1=xTree[num].e;
if((s1+e1)/2>=xco)
{
if(xTree[num].left==-1)
{
xTree[num].left=xTree.size();
xTree.push_back({s1,(s1+e1)/2,-1,-1,-1,0});
}
xup(xTree[num].left,xco,yco,v);
}
else
{
if(xTree[num].right==-1)
{
xTree[num].right=xTree.size();
xTree.push_back({(s1+e1)/2+1,e1,-1,-1,-1,0});
}
xup(xTree[num].right,xco,yco,v);
}
}
long long yans(int num,int px,int qx,int py,int qy)
{
if(yTree[num].s>qy||yTree[num].e<py)return 0ll;
if(py<=yTree[num].s&&yTree[num].e<=qy)return yTree[num].val;
long long l=0,r=0;
if(yTree[num].left>=0)l=yans(yTree[num].left,px,qx,py,qy);
if(yTree[num].right>=0)r=yans(yTree[num].right,px,qx,py,qy);
return gcd2(l,r);
}
long long xans(int num,int px,int qx,int py,int qy)
{
if(xTree[num].s>qx||xTree[num].e<px)return 0ll;
if(px<=xTree[num].s&&xTree[num].e<=qx)
{
if(xTree[num].ynum>=0)return yans(xTree[num].ynum,px,qx,py,qy);
else return 0ll;
}
long long l=0,r=0;
if(xTree[num].left>=0)l=xans(xTree[num].left,px,qx,py,qy);
if(xTree[num].right>=0)r=xans(xTree[num].right,px,qx,py,qy);
return gcd2(l,r);
}
void init(int R, int C)
{
a=R;b=C;X=1e9;
xTree.push_back({0,X,-1,-1,0,0});
yTree.push_back({0,X,-1,-1,-1,0});
}
void update(int P, int Q, long long K)
{
xup(0,P,Q,K);
}
long long calculate (int P, int Q, int U, int V)
{
return xans(0,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 function ‘void yup(int, int, int, long long int)’:
game.cpp:26:29: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
yTree.push_back({s1,(s1+e1)/2,-1,-1,-1,0});
^
game.cpp:26:54: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
yTree.push_back({s1,(s1+e1)/2,-1,-1,-1,0});
^
game.cpp:35:29: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
yTree.push_back({(s1+e1)/2+1,e1,-1,-1,-1,0});
^
game.cpp:35:56: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
yTree.push_back({(s1+e1)/2+1,e1,-1,-1,-1,0});
^
game.cpp: In function ‘void xup(int, int, int, long long int)’:
game.cpp:49:25: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
yTree.push_back({0,X,-1,-1,-1,0});
^
game.cpp:49:41: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
yTree.push_back({0,X,-1,-1,-1,0});
^
game.cpp:59:29: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
xTree.push_back({s1,(s1+e1)/2,-1,-1,-1,0});
^
game.cpp:59:54: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
xTree.push_back({s1,(s1+e1)/2,-1,-1,-1,0});
^
game.cpp:68:29: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
xTree.push_back({(s1+e1)/2+1,e1,-1,-1,-1,0});
^
game.cpp:68:56: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
xTree.push_back({(s1+e1)/2+1,e1,-1,-1,-1,0});
^
game.cpp: In function ‘void init(int, int)’:
game.cpp:98:21: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
xTree.push_back({0,X,-1,-1,0,0});
^
game.cpp:98:36: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
xTree.push_back({0,X,-1,-1,0,0});
^
game.cpp:99:21: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
yTree.push_back({0,X,-1,-1,-1,0});
^
game.cpp:99:37: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
yTree.push_back({0,X,-1,-1,-1,0});
^
/tmp/ccpwt1or.o: In function `main':
grader.c:(.text.startup+0x54): undefined reference to `init'
grader.c:(.text.startup+0xa8): undefined reference to `calculate'
grader.c:(.text.startup+0x112): undefined reference to `update'
collect2: error: ld returned 1 exit status
