oj.uz

답안 #308078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
308078 2020-09-30T02:53:42 Z daniel920712 게임 (IOI13_game) C++14
80 / 100
 6204 ms 256000 KB 
#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;
}

Compilation message

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 599 ms 10872 KB Output is correct
5 Correct 496 ms 11000 KB Output is correct
6 Correct 460 ms 7800 KB Output is correct
7 Correct 523 ms 7544 KB Output is correct
8 Correct 347 ms 5624 KB Output is correct
9 Correct 502 ms 7672 KB Output is correct
10 Correct 472 ms 7160 KB Output is correct
11 Correct 0 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1063 ms 13132 KB Output is correct
13 Correct 1746 ms 5112 KB Output is correct
14 Correct 310 ms 888 KB Output is correct
15 Correct 2106 ms 7144 KB Output is correct
16 Correct 218 ms 13944 KB Output is correct
17 Correct 773 ms 9208 KB Output is correct
18 Correct 1378 ms 14456 KB Output is correct
19 Correct 1164 ms 14584 KB Output is correct
20 Correct 1102 ms 14208 KB Output is correct
21 Correct 0 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 613 ms 10744 KB Output is correct
13 Correct 499 ms 11128 KB Output is correct
14 Correct 465 ms 7800 KB Output is correct
15 Correct 528 ms 7544 KB Output is correct
16 Correct 353 ms 5680 KB Output is correct
17 Correct 508 ms 7800 KB Output is correct
18 Correct 503 ms 7184 KB Output is correct
19 Correct 1108 ms 13068 KB Output is correct
20 Correct 1807 ms 4952 KB Output is correct
21 Correct 328 ms 900 KB Output is correct
22 Correct 2215 ms 6892 KB Output is correct
23 Correct 234 ms 14072 KB Output is correct
24 Correct 922 ms 9048 KB Output is correct
25 Correct 1568 ms 14516 KB Output is correct
26 Correct 1251 ms 14632 KB Output is correct
27 Correct 1184 ms 14200 KB Output is correct
28 Correct 838 ms 189048 KB Output is correct
29 Correct 1998 ms 220268 KB Output is correct
30 Correct 6118 ms 160132 KB Output is correct
31 Correct 5905 ms 124104 KB Output is correct
32 Correct 564 ms 10488 KB Output is correct
33 Correct 725 ms 12280 KB Output is correct
34 Correct 519 ms 214008 KB Output is correct
35 Correct 1349 ms 115192 KB Output is correct
36 Correct 2554 ms 218212 KB Output is correct
37 Correct 2071 ms 218488 KB Output is correct
38 Correct 2050 ms 218140 KB Output is correct
39 Correct 1760 ms 169956 KB Output is correct
40 Correct 0 ms 256 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 598 ms 10616 KB Output is correct
13 Correct 501 ms 11128 KB Output is correct
14 Correct 465 ms 7900 KB Output is correct
15 Correct 532 ms 7544 KB Output is correct
16 Correct 345 ms 5624 KB Output is correct
17 Correct 508 ms 7800 KB Output is correct
18 Correct 479 ms 7288 KB Output is correct
19 Correct 1072 ms 13048 KB Output is correct
20 Correct 1755 ms 5032 KB Output is correct
21 Correct 313 ms 888 KB Output is correct
22 Correct 2121 ms 6872 KB Output is correct
23 Correct 222 ms 13944 KB Output is correct
24 Correct 774 ms 9336 KB Output is correct
25 Correct 1357 ms 14584 KB Output is correct
26 Correct 1154 ms 14456 KB Output is correct
27 Correct 1120 ms 14072 KB Output is correct
28 Correct 830 ms 189176 KB Output is correct
29 Correct 1988 ms 220564 KB Output is correct
30 Correct 6204 ms 160060 KB Output is correct
31 Correct 5931 ms 123904 KB Output is correct
32 Correct 557 ms 10488 KB Output is correct
33 Correct 738 ms 12440 KB Output is correct
34 Correct 513 ms 214008 KB Output is correct
35 Correct 1393 ms 115028 KB Output is correct
36 Correct 2567 ms 218232 KB Output is correct
37 Correct 2052 ms 218404 KB Output is correct
38 Correct 2064 ms 217848 KB Output is correct
39 Runtime error 817 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -