제출 #308078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
308078		daniel920712	게임 (IOI13_game)	C++14	80 / 100	6204 ms	256000 KiB

game

#include "game.h"
#include <stdio.h>
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct A
{
    int nxl,nxr,nxt;
    long long con;
}Node[9000005];
long long N,M,now=1;
void New(int l,int r,int here,int t)
{
    Node[here].nxt=t;
    Node[here].nxl=-1;
    Node[here].nxr=-1;
    Node[here].con=0;
}
void init(int R, int C)
{
    N=R;
    M=C;
    New(0,N-1,0,-1);
}
void Merge(int here,int l,int r,int what,int lll,int rrr)
{
    int ll,rr;
    if(what==lll&&what==rrr)
    {
        Node[here].con=0;
        if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con);
        if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con);
        return;
    }
    if(what<=(lll+rrr)/2)
    {
        if(Node[here].nxl==-1)
        {
            Node[here].nxl=now++;
            New(lll,(lll+rrr)/2,Node[here].nxl,-2);
        }
        if(l!=-1) ll=Node[l].nxl;
        if(r!=-1) rr=Node[r].nxl;
        Merge(Node[here].nxl,ll,rr,what,lll,(lll+rrr)/2);
        Node[here].con=0;
        if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con);
        if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con);
    }
    else
    {
        if(Node[here].nxr==-1)
        {
            Node[here].nxr=now++;
            New((lll+rrr)/2+1,rrr,Node[here].nxr,-2);
        }
        if(l!=-1) ll=Node[l].nxr;
        if(r!=-1) rr=Node[r].nxr;
        Merge(Node[here].nxr,ll,rr,what,(lll+rrr)/2+1,rrr);
        Node[here].con=0;
        if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con);
        if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con);
    }
    //printf("%d %d %d\n",lll,rrr,Node[here].con);
}
void cha(int l,int r,int x,int y,long long con,int here)
{
    if(Node[here].nxt==-2)
    {
        if(y==l&&y==r)
        {
            Node[here].con=con;
            return;
        }
        if(y<=(l+r)/2)
        {
            if(Node[here].nxl==-1)
            {
                Node[here].nxl=now++;
                New(l,(l+r)/2,Node[here].nxl,-2);
            }
            cha(l,(l+r)/2,x,y,con,Node[here].nxl);
            Node[here].con=Node[Node[here].nxl].con;
            if(Node[here].nxr!=-1) Node[here].con=gcd2(Node[here].con,Node[Node[here].nxr].con);

        }
        else
        {
            if(Node[here].nxr==-1)
            {
                Node[here].nxr=now++;
                New((l+r)/2+1,r,Node[here].nxr,-2);
            }
            cha((l+r)/2+1,r,x,y,con,Node[here].nxr);
            Node[here].con=Node[Node[here].nxr].con;
            if(Node[here].nxl!=-1) Node[here].con=gcd2(Node[here].con,Node[Node[here].nxl].con);
        }
        //if(y==76) printf("%lld %lld %lld %lld\n",y,l,r,Node[here].con);
    }
    else
    {
        if(x==l&&x==r)
        {
            if(Node[here].nxt==-1)
            {
                Node[here].nxt=now++;
                New(0,M-1,Node[here].nxt,-2);
            }
            cha(0,M-1,x,y,con,Node[here].nxt);
            return;
        }
        if(x<=(l+r)/2)
        {
            if(Node[here].nxl==-1)
            {
                Node[here].nxl=now++;
                New(l,(l+r)/2,Node[here].nxl,-1);
            }
            cha(l,(l+r)/2,x,y,con,Node[here].nxl);
        }
        else
        {
            if(Node[here].nxr==-1)
            {
                Node[here].nxr=now++;
                New((l+r)/2+1,r,Node[here].nxr,-1);
            }
            cha((l+r)/2+1,r,x,y,con,Node[here].nxr);
        }
        if(Node[here].nxt==-1)
        {
            Node[here].nxt=now++;
            New(0,M-1,Node[here].nxt,-2);
        }
        //printf("aa %d %d\n",l,r);
        Merge(Node[here].nxt,Node[Node[here].nxl].nxt,Node[Node[here].nxr].nxt,y,0,M-1);
    }
}
long long Find(int l,int r,int x1,int y1,int x2,int y2,int here)
{
    //printf("%lld %lld %lld %lld %lld\n",x1,y1,x2,y2,here);
    if(here==-1) return 0;
    if(Node[here].nxt==-2)
    {
        if(l==x2&&r==y2)
        {
            //printf("%lld %lld %lld\n",x2,y2,Node[here].con);
            return Node[here].con;
        }
        if(y2<=(l+r)/2) return Find(l,(l+r)/2,x1,y1,x2,y2,Node[here].nxl);
        if(x2>(l+r)/2) return Find((l+r)/2+1,r,x1,y1,x2,y2,Node[here].nxr);
        return gcd2(Find(l,(l+r)/2,x1,y1,x2,(l+r)/2,Node[here].nxl),Find((l+r)/2+1,r,x1,y1,(l+r)/2+1,y2,Node[here].nxr));
    }
    else
    {
        if(l==x1&&r==y1) return Find(0,M-1,x1,y1,x2,y2,Node[here].nxt);
        if(y1<=(l+r)/2) return Find(l,(l+r)/2,x1,y1,x2,y2,Node[here].nxl);
        if(x1>(l+r)/2) return Find((l+r)/2+1,r,x1,y1,x2,y2,Node[here].nxr);
        return gcd2(Find(l,(l+r)/2,x1,(l+r)/2,x2,y2,Node[here].nxl),Find((l+r)/2+1,r,(l+r)/2+1,y1,x2,y2,Node[here].nxr));
    }
}
void update(int P, int Q, long long K)
{
    cha(0,N-1,P,Q,K,0);
}

long long calculate(int P, int Q, int U, int V)
{
    long long ans=0,i;
    //printf("aaa\n");
    ans=Find(0,N-1,P,U,Q,V,0);
    /*for(i=P;i<=U;i++)
    {
        ans=gcd2(ans,Find(i,i,Q,V,0));

        //if(P==60) printf("%lld %lld\n",i,Find(i,i,Q,V,0));


    }*/
    //printf("cc %lld\n",ans);
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'long long int calculate(int, int, int, int)':
game.cpp:174:21: warning: unused variable 'i' [-Wunused-variable]
  174 |     long long ans=0,i;
      |                     ^
game.cpp: In function 'void Merge(int, int, int, int, int, int)':
game.cpp:50:14: warning: 'll' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |         Merge(Node[here].nxl,ll,rr,what,lll,(lll+rrr)/2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:50:14: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20