oj.uz

Submission #18957

# Submission time Handle Problem Language Result Execution time Memory
18957 2016-02-16T17:59:09 Z ggoh Game (IOI13_game) C++
63 / 100
 3980 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

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 1996 KB Output is correct
10 Correct 0 ms 1604 KB Output is correct
11 Correct 2 ms 1604 KB Output is correct
12 Correct 0 ms 1344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory 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 1377 ms 99528 KB Output is correct
5 Correct 1043 ms 99528 KB Output is correct
6 Correct 1355 ms 99528 KB Output is correct
7 Correct 1400 ms 99524 KB Output is correct
8 Correct 940 ms 50376 KB Output is correct
9 Correct 1401 ms 99528 KB Output is correct
10 Correct 1331 ms 99528 KB Output is correct
11 Correct 0 ms 1344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory 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 1 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 1 ms 1604 KB Output is correct
11 Correct 1 ms 1604 KB Output is correct
12 Correct 2255 ms 25804 KB Output is correct
13 Correct 3504 ms 13516 KB Output is correct
14 Correct 848 ms 1996 KB Output is correct
15 Correct 3901 ms 26052 KB Output is correct
16 Correct 890 ms 50624 KB Output is correct
17 Correct 1988 ms 26052 KB Output is correct
18 Correct 2892 ms 50628 KB Output is correct
19 Correct 2602 ms 50628 KB Output is correct
20 Correct 2454 ms 50628 KB Output is correct
21 Correct 0 ms 1344 KB Output is correct

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory 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 0 ms 1996 KB Output is correct
10 Correct 0 ms 1604 KB Output is correct
11 Correct 1 ms 1604 KB Output is correct
12 Correct 1381 ms 99528 KB Output is correct
13 Correct 1036 ms 99528 KB Output is correct
14 Correct 1387 ms 99528 KB Output is correct
15 Correct 1418 ms 99524 KB Output is correct
16 Correct 974 ms 50376 KB Output is correct
17 Correct 1408 ms 99528 KB Output is correct
18 Correct 1310 ms 99528 KB Output is correct
19 Correct 2242 ms 25804 KB Output is correct
20 Correct 3472 ms 13516 KB Output is correct
21 Correct 862 ms 1996 KB Output is correct
22 Correct 3915 ms 26052 KB Output is correct
23 Correct 910 ms 50624 KB Output is correct
24 Correct 1979 ms 26052 KB Output is correct
25 Correct 2858 ms 50628 KB Output is correct
26 Correct 2667 ms 50628 KB Output is correct
27 Correct 2526 ms 50628 KB Output is correct
28 Memory limit exceeded 442 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1212 KB Output is correct
2 Correct 3 ms 1992 KB Output is correct
3 Correct 2 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 1 ms 1604 KB Output is correct
11 Correct 0 ms 1604 KB Output is correct
12 Correct 1466 ms 99528 KB Output is correct
13 Correct 1090 ms 99528 KB Output is correct
14 Correct 1414 ms 99528 KB Output is correct
15 Correct 1429 ms 99524 KB Output is correct
16 Correct 958 ms 50376 KB Output is correct
17 Correct 1377 ms 99528 KB Output is correct
18 Correct 1293 ms 99528 KB Output is correct
19 Correct 2241 ms 25804 KB Output is correct
20 Correct 3523 ms 13516 KB Output is correct
21 Correct 865 ms 1996 KB Output is correct
22 Correct 3980 ms 26052 KB Output is correct
23 Correct 891 ms 50624 KB Output is correct
24 Correct 2045 ms 26052 KB Output is correct
25 Correct 3051 ms 50628 KB Output is correct
26 Incorrect 2841 ms 50628 KB Output isn't correct - wrong output format : File not found: "/var/www/temp/18957/outputopy5_1"
27 Halted 0 ms 0 KB -
28 Memory limit exceeded 448 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -