oj.uz

Submission #308072

# Submission time Handle Problem Language Result Execution time Memory
308072 2020-09-30T02:42:23 Z daniel920712 Game (IOI13_game) C++14
63 / 100
 2005 ms 256004 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
{
    long long l,r;
    long long nxl,nxr,nxt;
    long long con;
}Node[10000005];
long long N,M,now=1;
void New(long long l,long long r,long long here,long long t)
{
    Node[here].l=l;
    Node[here].r=r;
    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(long long here,long long l,long long r,long long what)
{
    int ll,rr;
    if(what==Node[here].l&&what==Node[here].r)
    {
        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<=(Node[here].l+Node[here].r)/2)
    {
        if(Node[here].nxl==-1)
        {
            Node[here].nxl=now++;
            New(Node[here].l,(Node[here].l+Node[here].r)/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);
        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((Node[here].l+Node[here].r)/2+1,Node[here].r,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);
        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",Node[here].l,Node[here].r,Node[here].con);
}
void cha(long long x,long long y,long long con,long long here)
{
    if(Node[here].nxt==-2)
    {
        if(y==Node[here].l&&y==Node[here].r)
        {
            Node[here].con=con;
            return;
        }
        if(y<=(Node[here].l+Node[here].r)/2)
        {
            if(Node[here].nxl==-1)
            {
                Node[here].nxl=now++;
                New(Node[here].l,(Node[here].l+Node[here].r)/2,Node[here].nxl,-2);
            }
            cha(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((Node[here].l+Node[here].r)/2+1,Node[here].r,Node[here].nxr,-2);
            }
            cha(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,Node[here].l,Node[here].r,Node[here].con);
    }
    else
    {
        if(x==Node[here].l&&x==Node[here].r)
        {
            if(Node[here].nxt==-1)
            {
                Node[here].nxt=now++;
                New(0,M-1,Node[here].nxt,-2);
            }
            cha(x,y,con,Node[here].nxt);
            return;
        }
        if(x<=(Node[here].l+Node[here].r)/2)
        {
            if(Node[here].nxl==-1)
            {
                Node[here].nxl=now++;
                New(Node[here].l,(Node[here].l+Node[here].r)/2,Node[here].nxl,-1);
            }
            cha(x,y,con,Node[here].nxl);
        }
        else
        {
            if(Node[here].nxr==-1)
            {
                Node[here].nxr=now++;
                New((Node[here].l+Node[here].r)/2+1,Node[here].r,Node[here].nxr,-1);
            }
            cha(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",Node[here].l,Node[here].r);
        Merge(Node[here].nxt,Node[Node[here].nxl].nxt,Node[Node[here].nxr].nxt,y);
    }
}
long long Find(long long x1,long long y1,long long x2,long long y2,long long here)
{
    //printf("%lld %lld %lld %lld %lld\n",x1,y1,x2,y2,here);
    if(here==-1) return 0;
    if(Node[here].nxt==-2)
    {
        if(Node[here].l==x2&&Node[here].r==y2)
        {
            //printf("%lld %lld %lld\n",x2,y2,Node[here].con);
            return Node[here].con;
        }
        if(y2<=(Node[here].l+Node[here].r)/2) return Find(x1,y1,x2,y2,Node[here].nxl);
        if(x2>(Node[here].l+Node[here].r)/2) return Find(x1,y1,x2,y2,Node[here].nxr);
        return gcd2(Find(x1,y1,x2,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find(x1,y1,(Node[here].l+Node[here].r)/2+1,y2,Node[here].nxr));
    }
    else
    {
        if(Node[here].l==x1&&Node[here].r==y1) return Find(x1,y1,x2,y2,Node[here].nxt);
        if(y1<=(Node[here].l+Node[here].r)/2) return Find(x1,y1,x2,y2,Node[here].nxl);
        if(x1>(Node[here].l+Node[here].r)/2) return Find(x1,y1,x2,y2,Node[here].nxr);
        return gcd2(Find(x1,(Node[here].l+Node[here].r)/2,x2,y2,Node[here].nxl),Find((Node[here].l+Node[here].r)/2+1,y1,x2,y2,Node[here].nxr));
    }
}
void update(int P, int Q, long long K)
{
    cha(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(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:177:21: warning: unused variable 'i' [-Wunused-variable]
  177 |     long long ans=0,i;
      |                     ^
game.cpp: In function 'void Merge(long long int, long long int, long long int, long long int)':
game.cpp:36:9: warning: 'll' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |     int ll,rr;
      |         ^~
game.cpp:53:14: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |         Merge(Node[here].nxl,ll,rr,what);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 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 512 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 0 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 651 ms 16896 KB Output is correct
5 Correct 520 ms 17272 KB Output is correct
6 Correct 574 ms 14328 KB Output is correct
7 Correct 655 ms 13944 KB Output is correct
8 Correct 413 ms 9208 KB Output is correct
9 Correct 632 ms 13960 KB Output is correct
10 Correct 605 ms 13688 KB Output is correct
11 Correct 0 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 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 512 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 488 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1088 ms 21600 KB Output is correct
13 Correct 1700 ms 8876 KB Output is correct
14 Correct 329 ms 1016 KB Output is correct
15 Correct 2005 ms 12736 KB Output is correct
16 Correct 244 ms 26872 KB Output is correct
17 Correct 975 ms 16556 KB Output is correct
18 Correct 1808 ms 27416 KB Output is correct
19 Correct 1550 ms 27412 KB Output is correct
20 Correct 1505 ms 26872 KB Output is correct
21 Correct 0 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 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 512 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 643 ms 16792 KB Output is correct
13 Correct 495 ms 17144 KB Output is correct
14 Correct 567 ms 14200 KB Output is correct
15 Correct 653 ms 13944 KB Output is correct
16 Correct 402 ms 9208 KB Output is correct
17 Correct 643 ms 14072 KB Output is correct
18 Correct 610 ms 13560 KB Output is correct
19 Correct 1079 ms 21624 KB Output is correct
20 Correct 1720 ms 8912 KB Output is correct
21 Correct 321 ms 1016 KB Output is correct
22 Correct 1981 ms 12732 KB Output is correct
23 Correct 242 ms 26872 KB Output is correct
24 Correct 1022 ms 16632 KB Output is correct
25 Correct 1869 ms 27440 KB Output is correct
26 Correct 1456 ms 27640 KB Output is correct
27 Correct 1398 ms 27000 KB Output is correct
28 Runtime error 607 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 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 512 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 640 ms 16888 KB Output is correct
13 Correct 500 ms 17144 KB Output is correct
14 Correct 548 ms 14200 KB Output is correct
15 Correct 674 ms 13944 KB Output is correct
16 Correct 400 ms 9080 KB Output is correct
17 Correct 613 ms 14212 KB Output is correct
18 Correct 573 ms 13560 KB Output is correct
19 Correct 1080 ms 21880 KB Output is correct
20 Correct 1703 ms 8952 KB Output is correct
21 Correct 320 ms 1020 KB Output is correct
22 Correct 1997 ms 12792 KB Output is correct
23 Correct 253 ms 27000 KB Output is correct
24 Correct 1008 ms 16632 KB Output is correct
25 Correct 1754 ms 27512 KB Output is correct
26 Correct 1467 ms 27640 KB Output is correct
27 Correct 1404 ms 26852 KB Output is correct
28 Runtime error 610 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -