oj.uz

Submission #62479

# Submission time Handle Problem Language Result Execution time Memory
62479 2018-07-28T18:20:14 Z ggoh Game (IOI13_game) C++
0 / 100
 4 ms 652 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){
        yTree[num].val=v;
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Incorrect 4 ms 616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 616 KB Output is correct
2 Incorrect 3 ms 616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 616 KB Output is correct
2 Incorrect 4 ms 652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 652 KB Output is correct
2 Incorrect 4 ms 652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 652 KB Output is correct
2 Incorrect 3 ms 652 KB Output isn't correct
3 Halted 0 ms 0 KB -