답안 #18958 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18958	2016-02-16T18:05:44 Z	ggoh	게임 (IOI13_game)	C++	63 / 100	3781 ms	256000 KB

game

#include "game.h"
#include<algorithm>
#include<vector>
int a,b,X,t;
struct A{
    int s,e,left,right;
    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 num1,int num2,int xco,int yco,long long v)
{
    int s1=yTree[num].s,e1=yTree[num].e;
    if(s1==e1){
        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((s1+e1)/2>=yco)
    {
        if(yTree[num].left==-1)
        {
            yTree[num].left=yTree.size();
            yTree.push_back({s1,(s1+e1)/2,-1,-1,0});
        }
        if(num1>=0)num1=yTree[num1].left;
        if(num2>=0)num2=yTree[num2].left;
        yup(yTree[num].left,num1,num2,xco,yco,v);
    }
    else
    {
        if(yTree[num].right==-1)
        {
            yTree[num].right=yTree.size();
            yTree.push_back({(s1+e1)/2+1,e1,-1,-1,0});
        }
        if(num1>=0)num1=yTree[num1].right;
        if(num2>=0)num2=yTree[num2].right;
        yup(yTree[num].right,num1,num2,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].val==-1)
    {
        xTree[num].val=yTree.size();
        yTree.push_back({0,X,-1,-1,0});
    }
    if(xTree[num].s==xTree[num].e)
    {
        yup(xTree[num].val,-1,-1,xco,yco,v);
        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});
        }
        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});
        }
        xup(xTree[num].right,xco,yco,v);
    }
    yup(xTree[num].val,xTree[num].left==-1?-1:xTree[xTree[num].left].val,xTree[num].right==-1?-1:xTree[xTree[num].right].val,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].val>=0)return yans(xTree[num].val,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=std::max(R,C)-1;
    xTree.push_back({0,X,-1,-1,0});
    yTree.push_back({0,X,-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);
}

Subtask #1
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	1212 KB	Output is correct
2	Correct	1404 KB	Output is correct
3	Correct	1404 KB	Output is correct
4	Correct	1212 KB	Output is correct
5	Correct	1212 KB	Output is correct
6	Correct	1404 KB	Output is correct
7	Correct	1212 KB	Output is correct
8	Correct	1212 KB	Output is correct
9	Correct	1404 KB	Output is correct
10	Correct	1212 KB	Output is correct
11	Correct	1212 KB	Output is correct
12	Correct	1212 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	1058 ms	38088 KB	Output is correct
5	Correct	775 ms	38088 KB	Output is correct
6	Correct	943 ms	38088 KB	Output is correct
7	Correct	1023 ms	38084 KB	Output is correct
8	Correct	704 ms	19656 KB	Output is correct
9	Correct	1012 ms	38088 KB	Output is correct
10	Correct	939 ms	38088 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1404 KB	Output is correct
3	Correct	0 ms	1404 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1404 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1404 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	1711 ms	19664 KB	Output is correct
13	Correct	3285 ms	10448 KB	Output is correct
14	Correct	423 ms	1404 KB	Output is correct
15	Correct	3761 ms	10628 KB	Output is correct
16	Correct	278 ms	38272 KB	Output is correct
17	Correct	1283 ms	19844 KB	Output is correct
18	Correct	1871 ms	38276 KB	Output is correct
19	Correct	1719 ms	38276 KB	Output is correct
20	Correct	1600 ms	38276 KB	Output is correct
21	Correct	0 ms	1212 KB	Output is correct

Subtask #4
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1404 KB	Output is correct
3	Correct	0 ms	1404 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1404 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1404 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	1062 ms	38088 KB	Output is correct
13	Correct	779 ms	38088 KB	Output is correct
14	Correct	977 ms	38088 KB	Output is correct
15	Correct	1001 ms	38084 KB	Output is correct
16	Correct	674 ms	19656 KB	Output is correct
17	Correct	1007 ms	38088 KB	Output is correct
18	Correct	952 ms	38088 KB	Output is correct
19	Correct	1715 ms	19664 KB	Output is correct
20	Correct	3257 ms	10448 KB	Output is correct
21	Correct	426 ms	1404 KB	Output is correct
22	Correct	3781 ms	10628 KB	Output is correct
23	Correct	287 ms	38272 KB	Output is correct
24	Correct	1291 ms	19844 KB	Output is correct
25	Correct	1843 ms	38276 KB	Output is correct
26	Correct	1708 ms	38276 KB	Output is correct
27	Correct	1599 ms	38276 KB	Output is correct
28	Memory limit exceeded	412 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1404 KB	Output is correct
3	Correct	0 ms	1404 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1404 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1404 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	1108 ms	38088 KB	Output is correct
13	Correct	787 ms	38088 KB	Output is correct
14	Correct	1002 ms	38088 KB	Output is correct
15	Correct	1026 ms	38084 KB	Output is correct
16	Correct	721 ms	19656 KB	Output is correct
17	Correct	1020 ms	38088 KB	Output is correct
18	Correct	936 ms	38088 KB	Output is correct
19	Correct	1748 ms	19664 KB	Output is correct
20	Correct	3248 ms	10448 KB	Output is correct
21	Correct	443 ms	1404 KB	Output is correct
22	Correct	3757 ms	10628 KB	Output is correct
23	Correct	300 ms	38272 KB	Output is correct
24	Correct	1293 ms	19844 KB	Output is correct
25	Correct	1954 ms	38276 KB	Output is correct
26	Incorrect	1785 ms	38276 KB	Output isn't correct - wrong output format : File not found: "/var/www/temp/18958/outputXaB5_1"
27	Halted	0 ms	0 KB	-
28	Memory limit exceeded	397 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

답안 #18958

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0.0 / 17.0

Subtask #5 0.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0.0 / 17.0

Subtask #5
0.0 / 20.0