oj.uz

Submission #62465

# Submission time Handle Problem Language Result Execution time Memory
62465 2018-07-28T17:54:54 Z ggoh Game (IOI13_game) C++
63 / 100
 4406 ms 257024 KB 
#include "game.h"
#include<algorithm>
#include<vector>
int a,b,X,t;
struct A{
    int left,right,ynum;
};
struct B{
    int 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 s,int e,int num1,int num2,int yco,long long v)
{
    if(s==e){
        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((s+e)/2>=yco)
    {
        if(yTree[num].left==-1)
        {
            yTree[num].left=yTree.size();
            yTree.push_back({-1,-1,0});
        }
        if(num1>=0)num1=yTree[num1].left;
        if(num2>=0)num2=yTree[num2].left;
        yup(yTree[num].left,s,(s+e)/2,num1,num2,yco,v);
    }
    else
    {
        if(yTree[num].right==-1)
        {
            yTree[num].right=yTree.size();
            yTree.push_back({-1,-1,0});
        }
        if(num1>=0)num1=yTree[num1].right;
        if(num2>=0)num2=yTree[num2].right;
        yup(yTree[num].right,(s+e)/2+1,e,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 s,int e,int xco,int yco,long long v)
{
    if(xTree[num].ynum==-1)
    {
        xTree[num].ynum=yTree.size();
        yTree.push_back({-1,-1,0});
    }
    if(s==e)
    {
        yup(xTree[num].ynum,0,X,-1,-1,yco,v);
        return ;
    }
    if((s+e)/2>=xco)
    {
        if(xTree[num].left==-1)
        {
            xTree[num].left=xTree.size();
            xTree.push_back({-1,-1,-1});
        }
        xup(xTree[num].left,s,(s+e)/2,xco,yco,v);
    }
    else
    {
        if(xTree[num].right==-1)
        {
            xTree[num].right=xTree.size();
            xTree.push_back({-1,-1,-1});
        }
        xup(xTree[num].right,(s+e)/2+1,e,xco,yco,v);
    }
    yup(xTree[num].ynum,0,X,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 s,int e,int py,int qy)
{
    if(s>qy||e<py)return 0ll;
    if(py<=s&&e<=qy)return yTree[num].val;
    long long l=0,r=0;
    if(yTree[num].left>=0)l=yans(yTree[num].left,s,(s+e)/2,py,qy);
    if(yTree[num].right>=0)r=yans(yTree[num].right,(s+e)/2+1,e,py,qy);
    return gcd2(l,r);
}
long long xans(int num,int s,int e,int px,int qx,int py,int qy)
{
    if(s>qx||e<px)return 0ll;
    if(px<=s&&e<=qx)
    {
        if(xTree[num].ynum>=0)return yans(xTree[num].ynum,0,X,py,qy);
        else return 0ll;
    }
    long long l=0,r=0;
    if(xTree[num].left>=0)l=xans(xTree[num].left,s,(s+e)/2,px,qx,py,qy);
    if(xTree[num].right>=0)r=xans(xTree[num].right,(s+e)/2+1,e,px,qx,py,qy);
    return gcd2(l,r);
}
void init(int R, int C)
{
    a=R;b=C;X=1e9;
    xTree.push_back({-1,-1,0});
    yTree.push_back({-1,-1,0});
}
void update(int P, int Q, long long K)
{
    xup(0,0,X,P,Q,K);
}
long long calculate (int P, int Q, int U, int V)
{
    return xans(0,0,X,P,U,Q,V);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 6 ms 872 KB Output is correct
3 Correct 7 ms 956 KB Output is correct
4 Correct 3 ms 956 KB Output is correct
5 Correct 2 ms 956 KB Output is correct
6 Correct 7 ms 956 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 3 ms 956 KB Output is correct
9 Correct 5 ms 1052 KB Output is correct
10 Correct 4 ms 1052 KB Output is correct
11 Correct 5 ms 1052 KB Output is correct
12 Correct 2 ms 1052 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1052 KB Output is correct
2 Correct 2 ms 1052 KB Output is correct
3 Correct 3 ms 1052 KB Output is correct
4 Correct 1449 ms 39168 KB Output is correct
5 Correct 1369 ms 43452 KB Output is correct
6 Correct 1819 ms 45968 KB Output is correct
7 Correct 1966 ms 46892 KB Output is correct
8 Correct 1063 ms 46892 KB Output is correct
9 Correct 1892 ms 57008 KB Output is correct
10 Correct 1830 ms 60916 KB Output is correct
11 Correct 3 ms 60916 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 60916 KB Output is correct
2 Correct 6 ms 60916 KB Output is correct
3 Correct 7 ms 60916 KB Output is correct
4 Correct 3 ms 60916 KB Output is correct
5 Correct 3 ms 60916 KB Output is correct
6 Correct 7 ms 60916 KB Output is correct
7 Correct 3 ms 60916 KB Output is correct
8 Correct 2 ms 60916 KB Output is correct
9 Correct 6 ms 60916 KB Output is correct
10 Correct 4 ms 60916 KB Output is correct
11 Correct 5 ms 60916 KB Output is correct
12 Correct 2229 ms 60916 KB Output is correct
13 Correct 3565 ms 60916 KB Output is correct
14 Correct 899 ms 60916 KB Output is correct
15 Correct 4029 ms 60916 KB Output is correct
16 Correct 940 ms 65812 KB Output is correct
17 Correct 2476 ms 66708 KB Output is correct
18 Correct 4406 ms 76200 KB Output is correct
19 Correct 3734 ms 83780 KB Output is correct
20 Correct 3416 ms 88908 KB Output is correct
21 Correct 3 ms 88908 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 88908 KB Output is correct
2 Correct 6 ms 88908 KB Output is correct
3 Correct 7 ms 88908 KB Output is correct
4 Correct 4 ms 88908 KB Output is correct
5 Correct 3 ms 88908 KB Output is correct
6 Correct 8 ms 88908 KB Output is correct
7 Correct 3 ms 88908 KB Output is correct
8 Correct 3 ms 88908 KB Output is correct
9 Correct 7 ms 88908 KB Output is correct
10 Correct 4 ms 88908 KB Output is correct
11 Correct 6 ms 88908 KB Output is correct
12 Correct 1497 ms 112716 KB Output is correct
13 Correct 1315 ms 116952 KB Output is correct
14 Correct 1522 ms 119256 KB Output is correct
15 Correct 1877 ms 120408 KB Output is correct
16 Correct 1130 ms 120408 KB Output is correct
17 Correct 1685 ms 130404 KB Output is correct
18 Correct 1719 ms 132348 KB Output is correct
19 Correct 2395 ms 132348 KB Output is correct
20 Correct 3134 ms 132348 KB Output is correct
21 Correct 670 ms 132348 KB Output is correct
22 Correct 3664 ms 132348 KB Output is correct
23 Correct 924 ms 132348 KB Output is correct
24 Correct 2384 ms 132348 KB Output is correct
25 Correct 4009 ms 132348 KB Output is correct
26 Correct 3696 ms 132348 KB Output is correct
27 Correct 3501 ms 132348 KB Output is correct
28 Correct 1506 ms 233380 KB Output is correct
29 Runtime error 3543 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -