oj.uz

답안 #18963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18963 2016-02-16T18:22:57 Z ggoh 게임 (IOI13_game) C++
63 / 100
 3947 ms 256000 KB 
#include "game.h"
#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 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,-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,-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].ynum==-1)
    {
        xTree[num].ynum=yTree.size();
        yTree.push_back({0,X,-1,-1,-1,0});
    }
    if(xTree[num].s==xTree[num].e)
    {
        yup(xTree[num].ynum,-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,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);
    }
    yup(xTree[num].ynum,xTree[num].left==-1?-1:xTree[xTree[num].left].ynum,xTree[num].right==-1?-1:xTree[xTree[num].right].ynum,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);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Correct 3 ms 1992 KB Output is correct
3 Correct 4 ms 1996 KB Output is correct
4 Correct 0 ms 1344 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 3 ms 1992 KB Output is correct
7 Correct 0 ms 1344 KB Output is correct
8 Correct 0 ms 1344 KB Output is correct
9 Correct 3 ms 1996 KB Output is correct
10 Correct 0 ms 1604 KB Output is correct
11 Correct 0 ms 1604 KB Output is correct
12 Correct 0 ms 1344 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 1344 KB Output is correct
3 Correct 0 ms 1344 KB Output is correct
4 Correct 1371 ms 99528 KB Output is correct
5 Correct 1064 ms 99528 KB Output is correct
6 Correct 1394 ms 99528 KB Output is correct
7 Correct 1399 ms 99524 KB Output is correct
8 Correct 981 ms 50376 KB Output is correct
9 Correct 1398 ms 99528 KB Output is correct
10 Correct 1293 ms 99528 KB Output is correct
11 Correct 0 ms 1344 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Correct 4 ms 1992 KB Output is correct
3 Correct 4 ms 1996 KB Output is correct
4 Correct 0 ms 1344 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 3 ms 1992 KB Output is correct
7 Correct 0 ms 1344 KB Output is correct
8 Correct 0 ms 1344 KB Output is correct
9 Correct 0 ms 1996 KB Output is correct
10 Correct 0 ms 1604 KB Output is correct
11 Correct 0 ms 1604 KB Output is correct
12 Correct 2252 ms 25804 KB Output is correct
13 Correct 3512 ms 13516 KB Output is correct
14 Correct 860 ms 1996 KB Output is correct
15 Correct 3907 ms 26052 KB Output is correct
16 Correct 898 ms 50624 KB Output is correct
17 Correct 1990 ms 26052 KB Output is correct
18 Correct 2871 ms 50628 KB Output is correct
19 Correct 2623 ms 50628 KB Output is correct
20 Correct 2529 ms 50628 KB Output is correct
21 Correct 0 ms 1344 KB Output is correct

Subtask #4
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1212 KB Output is correct
2 Correct 3 ms 1992 KB Output is correct
3 Correct 0 ms 1996 KB Output is correct
4 Correct 0 ms 1344 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 0 ms 1992 KB Output is correct
7 Correct 0 ms 1344 KB Output is correct
8 Correct 0 ms 1344 KB Output is correct
9 Correct 3 ms 1996 KB Output is correct
10 Correct 0 ms 1604 KB Output is correct
11 Correct 0 ms 1604 KB Output is correct
12 Correct 1376 ms 99528 KB Output is correct
13 Correct 1092 ms 99528 KB Output is correct
14 Correct 1362 ms 99528 KB Output is correct
15 Correct 1379 ms 99524 KB Output is correct
16 Correct 944 ms 50376 KB Output is correct
17 Correct 1394 ms 99528 KB Output is correct
18 Correct 1298 ms 99528 KB Output is correct
19 Correct 2239 ms 25804 KB Output is correct
20 Correct 3448 ms 13516 KB Output is correct
21 Correct 863 ms 1996 KB Output is correct
22 Correct 3947 ms 26052 KB Output is correct
23 Correct 908 ms 50624 KB Output is correct
24 Correct 1968 ms 26052 KB Output is correct
25 Correct 2884 ms 50628 KB Output is correct
26 Correct 2631 ms 50628 KB Output is correct
27 Correct 2446 ms 50628 KB Output is correct
28 Memory limit exceeded 431 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 3 ms 1992 KB Output is correct
3 Correct 4 ms 1996 KB Output is correct
4 Correct 0 ms 1344 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 3 ms 1992 KB Output is correct
7 Correct 0 ms 1344 KB Output is correct
8 Correct 0 ms 1344 KB Output is correct
9 Correct 3 ms 1996 KB Output is correct
10 Correct 0 ms 1604 KB Output is correct
11 Correct 0 ms 1604 KB Output is correct
12 Correct 1435 ms 99528 KB Output is correct
13 Correct 1067 ms 99528 KB Output is correct
14 Correct 1392 ms 99528 KB Output is correct
15 Correct 1442 ms 99524 KB Output is correct
16 Correct 979 ms 50376 KB Output is correct
17 Correct 1408 ms 99528 KB Output is correct
18 Correct 1456 ms 99528 KB Output is correct
19 Correct 2258 ms 25804 KB Output is correct
20 Correct 3523 ms 13516 KB Output is correct
21 Correct 843 ms 1996 KB Output is correct
22 Correct 3941 ms 26052 KB Output is correct
23 Correct 905 ms 50624 KB Output is correct
24 Correct 2060 ms 26052 KB Output is correct
25 Correct 3097 ms 50628 KB Output is correct
26 Correct 2965 ms 50628 KB Output is correct
27 Incorrect 2662 ms 50628 KB Output isn't correct - wrong output format : File not found: "/var/www/temp/18963/outputCER5_1"
28 Halted 0 ms 0 KB -
29 Halted 0 ms 0 KB -