oj.uz

Submission #62464

# Submission time Handle Problem Language Result Execution time Memory
62464 2018-07-28T17:31:08 Z ggoh Game (IOI13_game) C++11
63 / 100
 4668 ms 257024 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);
}

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 376 KB Output is correct
2 Correct 7 ms 940 KB Output is correct
3 Correct 7 ms 940 KB Output is correct
4 Correct 4 ms 940 KB Output is correct
5 Correct 3 ms 940 KB Output is correct
6 Correct 6 ms 1084 KB Output is correct
7 Correct 3 ms 1084 KB Output is correct
8 Correct 3 ms 1084 KB Output is correct
9 Correct 6 ms 1160 KB Output is correct
10 Correct 4 ms 1160 KB Output is correct
11 Correct 5 ms 1160 KB Output is correct
12 Correct 3 ms 1160 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1160 KB Output is correct
2 Correct 2 ms 1160 KB Output is correct
3 Correct 3 ms 1160 KB Output is correct
4 Correct 1493 ms 55644 KB Output is correct
5 Correct 1124 ms 60176 KB Output is correct
6 Correct 1879 ms 62592 KB Output is correct
7 Correct 1797 ms 63604 KB Output is correct
8 Correct 1251 ms 63604 KB Output is correct
9 Correct 2017 ms 73712 KB Output is correct
10 Correct 1788 ms 77400 KB Output is correct
11 Correct 2 ms 77400 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 77400 KB Output is correct
2 Correct 7 ms 77400 KB Output is correct
3 Correct 6 ms 77400 KB Output is correct
4 Correct 3 ms 77400 KB Output is correct
5 Correct 3 ms 77400 KB Output is correct
6 Correct 6 ms 77400 KB Output is correct
7 Correct 4 ms 77400 KB Output is correct
8 Correct 3 ms 77400 KB Output is correct
9 Correct 5 ms 77400 KB Output is correct
10 Correct 4 ms 77400 KB Output is correct
11 Correct 5 ms 77400 KB Output is correct
12 Correct 2163 ms 77400 KB Output is correct
13 Correct 3389 ms 77400 KB Output is correct
14 Correct 857 ms 77400 KB Output is correct
15 Correct 4159 ms 77400 KB Output is correct
16 Correct 935 ms 77400 KB Output is correct
17 Correct 2687 ms 77400 KB Output is correct
18 Correct 4515 ms 84780 KB Output is correct
19 Correct 3901 ms 92392 KB Output is correct
20 Correct 3749 ms 97408 KB Output is correct
21 Correct 5 ms 97408 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 97408 KB Output is correct
2 Correct 7 ms 97408 KB Output is correct
3 Correct 7 ms 97408 KB Output is correct
4 Correct 2 ms 97408 KB Output is correct
5 Correct 3 ms 97408 KB Output is correct
6 Correct 7 ms 97408 KB Output is correct
7 Correct 2 ms 97408 KB Output is correct
8 Correct 4 ms 97408 KB Output is correct
9 Correct 5 ms 97408 KB Output is correct
10 Correct 4 ms 97408 KB Output is correct
11 Correct 5 ms 97408 KB Output is correct
12 Correct 1710 ms 129448 KB Output is correct
13 Correct 1265 ms 133532 KB Output is correct
14 Correct 1967 ms 135948 KB Output is correct
15 Correct 1912 ms 136696 KB Output is correct
16 Correct 1251 ms 136696 KB Output is correct
17 Correct 2263 ms 145516 KB Output is correct
18 Correct 1882 ms 148744 KB Output is correct
19 Correct 2478 ms 148744 KB Output is correct
20 Correct 3665 ms 148744 KB Output is correct
21 Correct 823 ms 148744 KB Output is correct
22 Correct 3873 ms 148744 KB Output is correct
23 Correct 890 ms 148744 KB Output is correct
24 Correct 2869 ms 148744 KB Output is correct
25 Correct 4668 ms 155912 KB Output is correct
26 Correct 4257 ms 162952 KB Output is correct
27 Correct 3847 ms 167128 KB Output is correct
28 Runtime error 1755 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.
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 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 -