oj.uz

Submission #18961

# Submission time Handle Problem Language Result Execution time Memory
18961 2016-02-16T18:16:29 Z ggoh Game (IOI13_game) C++
0 / 100
 3 ms 1796 KB 
#include "game.h"
#include<algorithm>
#include<vector>
int p,q,uu,vv,X,t;
long long k;
struct A{
    int s,e,left,right;
    long long val;
};
std::vector<A>xTree,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)
{
    if(yTree[num].s==yTree[num].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((yTree[num].s+yTree[num].e)/2>=yco)
    {
        if(yTree[num].left==-1)
        {
            yTree[num].left=yTree.size();
            yTree.push_back({yTree[num].s,(yTree[num].s+yTree[num].e)/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({(yTree[num].s+yTree[num].e)/2+1,yTree[num].e,-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=0;
    if(yTree[num].left>=0)yTree[num].val=gcd2(yTree[yTree[num].left].val,yTree[num].val);
    if(yTree[num].right>=0)yTree[num].val=gcd2(yTree[yTree[num].right].val,yTree[num].val);
    
}
void xup(int num,int xco)
{
    if(xTree[num].val==-1)
    {
        xTree[num].val=yTree.size();
        yTree.push_back({0,X,-1,-1,0});
    }
    if(xTree[num].s==xTree[num].e)
    {
        yup(xTree[num].val,-1,-1,q,k);
        return ;
    }
    if((xTree[num].s+xTree[num].e)/2>=xco)
    {
        if(xTree[num].left==-1)
        {
            xTree[num].left=xTree.size();
            xTree.push_back({xTree[num].s,(xTree[num].s+xTree[num].e)/2,-1,-1,-1});
        }
        xup(xTree[num].left,xco);
    }
    else
    {
        if(xTree[num].right==-1)
        {
            xTree[num].right=xTree.size();
            xTree.push_back({(xTree[num].s+xTree[num].e)/2+1,xTree[num].e,-1,-1,-1});
        }
        xup(xTree[num].right,xco);
    }
    yup(xTree[num].val,xTree[num].left==-1?-1:xTree[xTree[num].left].val,xTree[num].right==-1?-1:xTree[xTree[num].right].val,q,k);
}
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 r=0;
    if(yTree[num].left>=0)r=gcd2(r,yans(yTree[num].left,py,qy));
    if(yTree[num].right>=0)r=gcd2(r,yans(yTree[num].right,py,qy));
    return r;
}
long long xans(int num,int px,int qx)
{
    if(xTree[num].s>qx||xTree[num].e<px)return 0ll;
    if(px<=xTree[num].s&&xTree[num].e<=qx)
    {
        if(xTree[num].val>=0)return yans(xTree[num].val,q,vv);
        else return 0ll;
    }
    long long r=0;
    if(xTree[num].left>=0)r=gcd2(r,xans(xTree[num].left,q,vv));
    if(xTree[num].right>=0)r=gcd2(r,xans(xTree[num].right,q,vv));
    return r;
}
void init(int R, int 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)
{
    q=Q;k=K;
    xup(0,P);
}
long long calculate (int P, int Q, int U, int V)
{
    q=Q;vv=V;
    return xans(0,P,U);
}

Subtask #1
0.0 / 10.0

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

Subtask #2
0.0 / 27.0

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

Subtask #3
0.0 / 26.0

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

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Incorrect 0 ms 1796 KB Output isn't correct
3 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 Incorrect 3 ms 1796 KB Output isn't correct
3 Halted 0 ms 0 KB -