oj.uz

Submission #18958

# Submission time Handle Problem Language Result Execution time Memory
18958 2016-02-16T18:05:44 Z ggoh Game (IOI13_game) C++
63 / 100
 3781 ms 256000 KB 
#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

# Verdict Execution time Memory 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 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 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -