# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
62465 |
2018-07-28T17:54:54 Z |
ggoh |
게임 (IOI13_game) |
C++ |
|
4406 ms |
257024 KB |
#include "game.h"
#include<algorithm>
#include<vector>
int a,b,X,t;
struct A{
int left,right,ynum;
};
struct B{
int left,right;long long val;
};
std::vector<A>xTree;
std::vector<B>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 s,int e,int num1,int num2,int yco,long long v)
{
if(s==e){
if(num1==-1&&num2==-1)yTree[num].val=v;
else yTree[num].val=gcd2(num1==-1?0:yTree[num1].val,num2==-1?0:yTree[num2].val);
return ;
}
if((s+e)/2>=yco)
{
if(yTree[num].left==-1)
{
yTree[num].left=yTree.size();
yTree.push_back({-1,-1,0});
}
if(num1>=0)num1=yTree[num1].left;
if(num2>=0)num2=yTree[num2].left;
yup(yTree[num].left,s,(s+e)/2,num1,num2,yco,v);
}
else
{
if(yTree[num].right==-1)
{
yTree[num].right=yTree.size();
yTree.push_back({-1,-1,0});
}
if(num1>=0)num1=yTree[num1].right;
if(num2>=0)num2=yTree[num2].right;
yup(yTree[num].right,(s+e)/2+1,e,num1,num2,yco,v);
}
yTree[num].val=gcd2(yTree[num].left>=0?yTree[yTree[num].left].val:0,yTree[num].right>=0?yTree[yTree[num].right].val:0);
}
void xup(int num,int s,int e,int xco,int yco,long long v)
{
if(xTree[num].ynum==-1)
{
xTree[num].ynum=yTree.size();
yTree.push_back({-1,-1,0});
}
if(s==e)
{
yup(xTree[num].ynum,0,X,-1,-1,yco,v);
return ;
}
if((s+e)/2>=xco)
{
if(xTree[num].left==-1)
{
xTree[num].left=xTree.size();
xTree.push_back({-1,-1,-1});
}
xup(xTree[num].left,s,(s+e)/2,xco,yco,v);
}
else
{
if(xTree[num].right==-1)
{
xTree[num].right=xTree.size();
xTree.push_back({-1,-1,-1});
}
xup(xTree[num].right,(s+e)/2+1,e,xco,yco,v);
}
yup(xTree[num].ynum,0,X,xTree[num].left==-1?-1:xTree[xTree[num].left].ynum,xTree[num].right==-1?-1:xTree[xTree[num].right].ynum,yco,v);
}
long long yans(int num,int s,int e,int py,int qy)
{
if(s>qy||e<py)return 0ll;
if(py<=s&&e<=qy)return yTree[num].val;
long long l=0,r=0;
if(yTree[num].left>=0)l=yans(yTree[num].left,s,(s+e)/2,py,qy);
if(yTree[num].right>=0)r=yans(yTree[num].right,(s+e)/2+1,e,py,qy);
return gcd2(l,r);
}
long long xans(int num,int s,int e,int px,int qx,int py,int qy)
{
if(s>qx||e<px)return 0ll;
if(px<=s&&e<=qx)
{
if(xTree[num].ynum>=0)return yans(xTree[num].ynum,0,X,py,qy);
else return 0ll;
}
long long l=0,r=0;
if(xTree[num].left>=0)l=xans(xTree[num].left,s,(s+e)/2,px,qx,py,qy);
if(xTree[num].right>=0)r=xans(xTree[num].right,(s+e)/2+1,e,px,qx,py,qy);
return gcd2(l,r);
}
void init(int R, int C)
{
a=R;b=C;X=1e9;
xTree.push_back({-1,-1,0});
yTree.push_back({-1,-1,0});
}
void update(int P, int Q, long long K)
{
xup(0,0,X,P,Q,K);
}
long long calculate (int P, int Q, int U, int V)
{
return xans(0,0,X,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;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
248 KB |
Output is correct |
2 |
Correct |
6 ms |
872 KB |
Output is correct |
3 |
Correct |
7 ms |
956 KB |
Output is correct |
4 |
Correct |
3 ms |
956 KB |
Output is correct |
5 |
Correct |
2 ms |
956 KB |
Output is correct |
6 |
Correct |
7 ms |
956 KB |
Output is correct |
7 |
Correct |
2 ms |
956 KB |
Output is correct |
8 |
Correct |
3 ms |
956 KB |
Output is correct |
9 |
Correct |
5 ms |
1052 KB |
Output is correct |
10 |
Correct |
4 ms |
1052 KB |
Output is correct |
11 |
Correct |
5 ms |
1052 KB |
Output is correct |
12 |
Correct |
2 ms |
1052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1052 KB |
Output is correct |
2 |
Correct |
2 ms |
1052 KB |
Output is correct |
3 |
Correct |
3 ms |
1052 KB |
Output is correct |
4 |
Correct |
1449 ms |
39168 KB |
Output is correct |
5 |
Correct |
1369 ms |
43452 KB |
Output is correct |
6 |
Correct |
1819 ms |
45968 KB |
Output is correct |
7 |
Correct |
1966 ms |
46892 KB |
Output is correct |
8 |
Correct |
1063 ms |
46892 KB |
Output is correct |
9 |
Correct |
1892 ms |
57008 KB |
Output is correct |
10 |
Correct |
1830 ms |
60916 KB |
Output is correct |
11 |
Correct |
3 ms |
60916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
60916 KB |
Output is correct |
2 |
Correct |
6 ms |
60916 KB |
Output is correct |
3 |
Correct |
7 ms |
60916 KB |
Output is correct |
4 |
Correct |
3 ms |
60916 KB |
Output is correct |
5 |
Correct |
3 ms |
60916 KB |
Output is correct |
6 |
Correct |
7 ms |
60916 KB |
Output is correct |
7 |
Correct |
3 ms |
60916 KB |
Output is correct |
8 |
Correct |
2 ms |
60916 KB |
Output is correct |
9 |
Correct |
6 ms |
60916 KB |
Output is correct |
10 |
Correct |
4 ms |
60916 KB |
Output is correct |
11 |
Correct |
5 ms |
60916 KB |
Output is correct |
12 |
Correct |
2229 ms |
60916 KB |
Output is correct |
13 |
Correct |
3565 ms |
60916 KB |
Output is correct |
14 |
Correct |
899 ms |
60916 KB |
Output is correct |
15 |
Correct |
4029 ms |
60916 KB |
Output is correct |
16 |
Correct |
940 ms |
65812 KB |
Output is correct |
17 |
Correct |
2476 ms |
66708 KB |
Output is correct |
18 |
Correct |
4406 ms |
76200 KB |
Output is correct |
19 |
Correct |
3734 ms |
83780 KB |
Output is correct |
20 |
Correct |
3416 ms |
88908 KB |
Output is correct |
21 |
Correct |
3 ms |
88908 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
88908 KB |
Output is correct |
2 |
Correct |
6 ms |
88908 KB |
Output is correct |
3 |
Correct |
7 ms |
88908 KB |
Output is correct |
4 |
Correct |
4 ms |
88908 KB |
Output is correct |
5 |
Correct |
3 ms |
88908 KB |
Output is correct |
6 |
Correct |
8 ms |
88908 KB |
Output is correct |
7 |
Correct |
3 ms |
88908 KB |
Output is correct |
8 |
Correct |
3 ms |
88908 KB |
Output is correct |
9 |
Correct |
7 ms |
88908 KB |
Output is correct |
10 |
Correct |
4 ms |
88908 KB |
Output is correct |
11 |
Correct |
6 ms |
88908 KB |
Output is correct |
12 |
Correct |
1497 ms |
112716 KB |
Output is correct |
13 |
Correct |
1315 ms |
116952 KB |
Output is correct |
14 |
Correct |
1522 ms |
119256 KB |
Output is correct |
15 |
Correct |
1877 ms |
120408 KB |
Output is correct |
16 |
Correct |
1130 ms |
120408 KB |
Output is correct |
17 |
Correct |
1685 ms |
130404 KB |
Output is correct |
18 |
Correct |
1719 ms |
132348 KB |
Output is correct |
19 |
Correct |
2395 ms |
132348 KB |
Output is correct |
20 |
Correct |
3134 ms |
132348 KB |
Output is correct |
21 |
Correct |
670 ms |
132348 KB |
Output is correct |
22 |
Correct |
3664 ms |
132348 KB |
Output is correct |
23 |
Correct |
924 ms |
132348 KB |
Output is correct |
24 |
Correct |
2384 ms |
132348 KB |
Output is correct |
25 |
Correct |
4009 ms |
132348 KB |
Output is correct |
26 |
Correct |
3696 ms |
132348 KB |
Output is correct |
27 |
Correct |
3501 ms |
132348 KB |
Output is correct |
28 |
Correct |
1506 ms |
233380 KB |
Output is correct |
29 |
Runtime error |
3543 ms |
257024 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
5 ms |
257024 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
2 |
Halted |
0 ms |
0 KB |
- |