oj.uz

Submission #18966

# Submission time Handle Problem Language Result Execution time Memory
18966 2016-02-16T18:27:49 Z ggoh Game (IOI13_game) C++
63 / 100
 3890 ms 256000 KB 
#include "game.h"
#include<algorithm>
#include<vector>
int a,b,X,t;
struct A{
    int s,e,left,right,ynum;
};
struct B{
    int s,e,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 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);
    }
    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,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});
        }
        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].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});
    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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Correct 4 ms 1796 KB Output is correct
3 Correct 4 ms 1800 KB Output is correct
4 Correct 0 ms 1212 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 4 ms 1796 KB Output is correct
7 Correct 0 ms 1212 KB Output is correct
8 Correct 0 ms 1212 KB Output is correct
9 Correct 3 ms 1800 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 1212 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 1212 KB Output is correct
3 Correct 0 ms 1212 KB Output is correct
4 Correct 1337 ms 74952 KB Output is correct
5 Correct 1032 ms 74952 KB Output is correct
6 Correct 1303 ms 74952 KB Output is correct
7 Correct 1361 ms 74948 KB Output is correct
8 Correct 938 ms 38088 KB Output is correct
9 Correct 1343 ms 74952 KB Output is correct
10 Correct 1258 ms 74952 KB Output is correct
11 Correct 0 ms 1212 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 1796 KB Output is correct
3 Correct 4 ms 1800 KB Output is correct
4 Correct 0 ms 1212 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 3 ms 1796 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 1800 KB Output is correct
10 Correct 0 ms 1604 KB Output is correct
11 Correct 0 ms 1604 KB Output is correct
12 Correct 2195 ms 19656 KB Output is correct
13 Correct 3411 ms 10440 KB Output is correct
14 Correct 863 ms 1800 KB Output is correct
15 Correct 3890 ms 19812 KB Output is correct
16 Correct 875 ms 38240 KB Output is correct
17 Correct 1905 ms 19812 KB Output is correct
18 Correct 2775 ms 38244 KB Output is correct
19 Correct 2519 ms 38244 KB Output is correct
20 Correct 2407 ms 38244 KB Output is correct
21 Correct 0 ms 1212 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 1796 KB Output is correct
3 Correct 4 ms 1800 KB Output is correct
4 Correct 0 ms 1212 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 3 ms 1796 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 1800 KB Output is correct
10 Correct 0 ms 1604 KB Output is correct
11 Correct 1 ms 1604 KB Output is correct
12 Correct 1324 ms 74952 KB Output is correct
13 Correct 1016 ms 74952 KB Output is correct
14 Correct 1321 ms 74952 KB Output is correct
15 Correct 1392 ms 74948 KB Output is correct
16 Correct 903 ms 38088 KB Output is correct
17 Correct 1350 ms 74952 KB Output is correct
18 Correct 1249 ms 74952 KB Output is correct
19 Correct 2146 ms 19656 KB Output is correct
20 Correct 3399 ms 10440 KB Output is correct
21 Correct 852 ms 1800 KB Output is correct
22 Correct 3867 ms 19812 KB Output is correct
23 Correct 871 ms 38240 KB Output is correct
24 Correct 1928 ms 19812 KB Output is correct
25 Correct 2759 ms 38244 KB Output is correct
26 Correct 2509 ms 38244 KB Output is correct
27 Correct 2394 ms 38244 KB Output is correct
28 Memory limit exceeded 402 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 0 ms 1796 KB Output is correct
3 Correct 4 ms 1800 KB Output is correct
4 Correct 0 ms 1212 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 3 ms 1796 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 1800 KB Output is correct
10 Correct 2 ms 1604 KB Output is correct
11 Correct 1 ms 1604 KB Output is correct
12 Correct 1378 ms 74952 KB Output is correct
13 Correct 1042 ms 74952 KB Output is correct
14 Correct 1341 ms 74952 KB Output is correct
15 Correct 1386 ms 74948 KB Output is correct
16 Correct 945 ms 38088 KB Output is correct
17 Correct 1357 ms 74952 KB Output is correct
18 Correct 1292 ms 74952 KB Output is correct
19 Correct 2185 ms 19656 KB Output is correct
20 Correct 3446 ms 10440 KB Output is correct
21 Correct 869 ms 1800 KB Output is correct
22 Correct 3853 ms 19812 KB Output is correct
23 Correct 861 ms 38240 KB Output is correct
24 Correct 1985 ms 19812 KB Output is correct
25 Correct 2917 ms 38244 KB Output is correct
26 Correct 2652 ms 38244 KB Output is correct
27 Incorrect 2353 ms 38244 KB Output isn't correct - wrong output format : File not found: "/var/www/temp/18966/outputG065_1"
28 Halted 0 ms 0 KB -
29 Halted 0 ms 0 KB -