oj.uz

Submission #18964

# Submission time Handle Problem Language Result Execution time Memory
18964 2016-02-16T18:24:32 Z ggoh Game (IOI13_game) C++
63 / 100
 3999 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);
    }
    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 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 0 ms 1212 KB Output is correct
2 Correct 3 ms 1992 KB Output is correct
3 Correct 3 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 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 1486 ms 99528 KB Output is correct
5 Correct 1089 ms 99528 KB Output is correct
6 Correct 1406 ms 99528 KB Output is correct
7 Correct 1414 ms 99524 KB Output is correct
8 Correct 949 ms 50376 KB Output is correct
9 Correct 1398 ms 99528 KB Output is correct
10 Correct 1316 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 1 ms 1212 KB Output is correct
2 Correct 3 ms 1992 KB Output is correct
3 Correct 3 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 2266 ms 25804 KB Output is correct
13 Correct 3513 ms 13516 KB Output is correct
14 Correct 855 ms 1996 KB Output is correct
15 Correct 3999 ms 26052 KB Output is correct
16 Correct 893 ms 50624 KB Output is correct
17 Correct 2176 ms 26052 KB Output is correct
18 Correct 3048 ms 50628 KB Output is correct
19 Correct 2647 ms 50628 KB Output is correct
20 Correct 2493 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 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 3 ms 1996 KB Output is correct
10 Correct 2 ms 1604 KB Output is correct
11 Correct 0 ms 1604 KB Output is correct
12 Correct 1353 ms 99528 KB Output is correct
13 Correct 1052 ms 99528 KB Output is correct
14 Correct 1369 ms 99528 KB Output is correct
15 Correct 1401 ms 99524 KB Output is correct
16 Correct 950 ms 50376 KB Output is correct
17 Correct 1379 ms 99528 KB Output is correct
18 Correct 1310 ms 99528 KB Output is correct
19 Correct 2225 ms 25804 KB Output is correct
20 Correct 3486 ms 13516 KB Output is correct
21 Correct 866 ms 1996 KB Output is correct
22 Correct 3962 ms 26052 KB Output is correct
23 Correct 888 ms 50624 KB Output is correct
24 Correct 1938 ms 26052 KB Output is correct
25 Correct 2879 ms 50628 KB Output is correct
26 Correct 2651 ms 50628 KB Output is correct
27 Correct 2524 ms 50628 KB Output is correct
28 Memory limit exceeded 387 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 0 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 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 1423 ms 99528 KB Output is correct
13 Correct 1100 ms 99528 KB Output is correct
14 Correct 1362 ms 99528 KB Output is correct
15 Correct 1492 ms 99524 KB Output is correct
16 Correct 969 ms 50376 KB Output is correct
17 Correct 1418 ms 99528 KB Output is correct
18 Correct 1332 ms 99528 KB Output is correct
19 Correct 2273 ms 25804 KB Output is correct
20 Correct 3485 ms 13516 KB Output is correct
21 Correct 877 ms 1996 KB Output is correct
22 Correct 3910 ms 26052 KB Output is correct
23 Correct 892 ms 50624 KB Output is correct
24 Correct 2051 ms 26052 KB Output is correct
25 Correct 3076 ms 50628 KB Output is correct
26 Incorrect 2783 ms 50628 KB Output isn't correct - wrong output format : File not found: "/var/www/temp/18964/outputtRK5_1"
27 Halted 0 ms 0 KB -
28 Memory limit exceeded 441 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -