oj.uz

Submission #62472

# Submission time Handle Problem Language Result Execution time Memory
62472 2018-07-28T18:04:07 Z ggoh Game (IOI13_game) C++
63 / 100
 4213 ms 257024 KB 
#include "game.h"
#include<algorithm>
#include<vector>
int a,b,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,b-1,-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,b-1,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,b-1,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;
    xTree.push_back({-1,-1,0});
    yTree.push_back({-1,-1,0});
}
void update(int P, int Q, long long K)
{
    xup(0,0,a-1,P,Q,K);
}
long long calculate (int P, int Q, int U, int V)
{
    return xans(0,0,a-1,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 2 ms 612 KB Output is correct
3 Correct 4 ms 656 KB Output is correct
4 Correct 3 ms 656 KB Output is correct
5 Correct 2 ms 656 KB Output is correct
6 Correct 4 ms 656 KB Output is correct
7 Correct 3 ms 656 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Correct 3 ms 656 KB Output is correct
10 Correct 4 ms 656 KB Output is correct
11 Correct 3 ms 656 KB Output is correct
12 Correct 3 ms 748 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1048 ms 17552 KB Output is correct
5 Correct 951 ms 21668 KB Output is correct
6 Correct 928 ms 23052 KB Output is correct
7 Correct 1166 ms 23640 KB Output is correct
8 Correct 653 ms 27524 KB Output is correct
9 Correct 999 ms 33068 KB Output is correct
10 Correct 972 ms 36884 KB Output is correct
11 Correct 2 ms 36884 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 36884 KB Output is correct
2 Correct 5 ms 36884 KB Output is correct
3 Correct 3 ms 36884 KB Output is correct
4 Correct 3 ms 36884 KB Output is correct
5 Correct 2 ms 36884 KB Output is correct
6 Correct 3 ms 36884 KB Output is correct
7 Correct 4 ms 36884 KB Output is correct
8 Correct 2 ms 36884 KB Output is correct
9 Correct 4 ms 36884 KB Output is correct
10 Correct 3 ms 36884 KB Output is correct
11 Correct 3 ms 36884 KB Output is correct
12 Correct 2152 ms 46084 KB Output is correct
13 Correct 3474 ms 46084 KB Output is correct
14 Correct 508 ms 46084 KB Output is correct
15 Correct 3936 ms 53764 KB Output is correct
16 Correct 307 ms 66048 KB Output is correct
17 Correct 1756 ms 66768 KB Output is correct
18 Correct 3035 ms 77236 KB Output is correct
19 Correct 2607 ms 86004 KB Output is correct
20 Correct 2550 ms 90944 KB Output is correct
21 Correct 2 ms 90944 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 90944 KB Output is correct
2 Correct 5 ms 90944 KB Output is correct
3 Correct 4 ms 90944 KB Output is correct
4 Correct 3 ms 90944 KB Output is correct
5 Correct 3 ms 90944 KB Output is correct
6 Correct 3 ms 90944 KB Output is correct
7 Correct 3 ms 90944 KB Output is correct
8 Correct 3 ms 90944 KB Output is correct
9 Correct 4 ms 90944 KB Output is correct
10 Correct 4 ms 90944 KB Output is correct
11 Correct 2 ms 90944 KB Output is correct
12 Correct 1186 ms 90944 KB Output is correct
13 Correct 803 ms 94804 KB Output is correct
14 Correct 990 ms 96332 KB Output is correct
15 Correct 1200 ms 96824 KB Output is correct
16 Correct 663 ms 101044 KB Output is correct
17 Correct 1029 ms 106388 KB Output is correct
18 Correct 925 ms 107512 KB Output is correct
19 Correct 1819 ms 110176 KB Output is correct
20 Correct 3416 ms 110176 KB Output is correct
21 Correct 423 ms 110176 KB Output is correct
22 Correct 3784 ms 110176 KB Output is correct
23 Correct 319 ms 115816 KB Output is correct
24 Correct 1955 ms 115816 KB Output is correct
25 Correct 3244 ms 116332 KB Output is correct
26 Correct 2490 ms 116972 KB Output is correct
27 Correct 2516 ms 116972 KB Output is correct
28 Correct 1577 ms 227312 KB Output is correct
29 Runtime error 4213 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 3 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 -