oj.uz

Submission #18967

# Submission time Handle Problem Language Result Execution time Memory
18967 2016-02-16T18:30:29 Z ggoh Game (IOI13_game) C++
63 / 100
 3671 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 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,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,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,  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,yco,v);
}
long long yans(int num,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,py,qy);
    if(yTree[num].right>=0)r=yans(yTree[num].right,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,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 2 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 0 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 1 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 1268 ms 74952 KB Output is correct
5 Correct 1002 ms 74952 KB Output is correct
6 Correct 1269 ms 74952 KB Output is correct
7 Correct 1331 ms 74948 KB Output is correct
8 Correct 878 ms 38088 KB Output is correct
9 Correct 1311 ms 74952 KB Output is correct
10 Correct 1264 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 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 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 3 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 2086 ms 19656 KB Output is correct
13 Correct 3252 ms 10440 KB Output is correct
14 Correct 821 ms 1800 KB Output is correct
15 Correct 3651 ms 19812 KB Output is correct
16 Correct 834 ms 38240 KB Output is correct
17 Correct 1842 ms 19812 KB Output is correct
18 Correct 2690 ms 38244 KB Output is correct
19 Correct 2457 ms 38244 KB Output is correct
20 Correct 2341 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 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 2 ms 1800 KB Output is correct
10 Correct 1 ms 1604 KB Output is correct
11 Correct 0 ms 1604 KB Output is correct
12 Correct 1303 ms 74952 KB Output is correct
13 Correct 1014 ms 74952 KB Output is correct
14 Correct 1284 ms 74952 KB Output is correct
15 Correct 1321 ms 74948 KB Output is correct
16 Correct 899 ms 38088 KB Output is correct
17 Correct 1329 ms 74952 KB Output is correct
18 Correct 1253 ms 74952 KB Output is correct
19 Correct 2027 ms 19656 KB Output is correct
20 Correct 3204 ms 10440 KB Output is correct
21 Correct 826 ms 1800 KB Output is correct
22 Correct 3629 ms 19812 KB Output is correct
23 Correct 845 ms 38240 KB Output is correct
24 Correct 1849 ms 19812 KB Output is correct
25 Correct 2655 ms 38244 KB Output is correct
26 Correct 2459 ms 38244 KB Output is correct
27 Correct 2294 ms 38244 KB Output is correct
28 Memory limit exceeded 351 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 0 ms 1604 KB Output is correct
11 Correct 1 ms 1604 KB Output is correct
12 Correct 1287 ms 74952 KB Output is correct
13 Correct 994 ms 74952 KB Output is correct
14 Correct 1277 ms 74952 KB Output is correct
15 Correct 1337 ms 74948 KB Output is correct
16 Correct 934 ms 38088 KB Output is correct
17 Correct 1333 ms 74952 KB Output is correct
18 Correct 1262 ms 74952 KB Output is correct
19 Correct 2067 ms 19656 KB Output is correct
20 Correct 3201 ms 10440 KB Output is correct
21 Correct 824 ms 1800 KB Output is correct
22 Correct 3671 ms 19812 KB Output is correct
23 Correct 879 ms 38240 KB Output is correct
24 Correct 1855 ms 19812 KB Output is correct
25 Correct 2782 ms 38244 KB Output is correct
26 Incorrect 2516 ms 38244 KB Output isn't correct - wrong output format : File not found: "/var/www/temp/18967/outputlU15_1"
27 Halted 0 ms 0 KB -
28 Memory limit exceeded 414 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -