oj.uz

Submission #308082

# Submission time Handle Problem Language Result Execution time Memory
308082 2020-09-30T02:57:26 Z daniel920712 Game (IOI13_game) C++14
80 / 100
 6157 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
{
    int nxl,nxr,nxt;
    long long con;
}Node[20250005];
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

# Verdict Execution time Memory 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 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 658 ms 10676 KB Output is correct
5 Correct 524 ms 10872 KB Output is correct
6 Correct 501 ms 8056 KB Output is correct
7 Correct 528 ms 7544 KB Output is correct
8 Correct 365 ms 5496 KB Output is correct
9 Correct 555 ms 7800 KB Output is correct
10 Correct 507 ms 7288 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 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 0 ms 384 KB Output is correct
12 Correct 1065 ms 13176 KB Output is correct
13 Correct 1759 ms 4976 KB Output is correct
14 Correct 308 ms 888 KB Output is correct
15 Correct 2135 ms 6932 KB Output is correct
16 Correct 218 ms 13944 KB Output is correct
17 Correct 791 ms 9080 KB Output is correct
18 Correct 1357 ms 14328 KB Output is correct
19 Correct 1185 ms 14456 KB Output is correct
20 Correct 1081 ms 13944 KB Output is correct
21 Correct 0 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory 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 1 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 256 KB Output is correct
12 Correct 596 ms 10616 KB Output is correct
13 Correct 509 ms 10872 KB Output is correct
14 Correct 468 ms 7800 KB Output is correct
15 Correct 539 ms 7672 KB Output is correct
16 Correct 349 ms 5496 KB Output is correct
17 Correct 505 ms 7672 KB Output is correct
18 Correct 488 ms 7288 KB Output is correct
19 Correct 1067 ms 13072 KB Output is correct
20 Correct 1782 ms 4948 KB Output is correct
21 Correct 307 ms 888 KB Output is correct
22 Correct 2207 ms 6864 KB Output is correct
23 Correct 223 ms 13944 KB Output is correct
24 Correct 886 ms 9112 KB Output is correct
25 Correct 1606 ms 14584 KB Output is correct
26 Correct 1276 ms 14584 KB Output is correct
27 Correct 1224 ms 13944 KB Output is correct
28 Correct 850 ms 189164 KB Output is correct
29 Correct 2015 ms 210224 KB Output is correct
30 Correct 6156 ms 152852 KB Output is correct
31 Correct 5867 ms 116916 KB Output is correct
32 Correct 556 ms 1272 KB Output is correct
33 Correct 720 ms 3064 KB Output is correct
34 Correct 512 ms 207224 KB Output is correct
35 Correct 1329 ms 105208 KB Output is correct
36 Correct 2555 ms 207668 KB Output is correct
37 Correct 2053 ms 207744 KB Output is correct
38 Correct 2066 ms 207480 KB Output is correct
39 Correct 1748 ms 159864 KB Output is correct
40 Correct 0 ms 256 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory 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 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 605 ms 10680 KB Output is correct
13 Correct 497 ms 10928 KB Output is correct
14 Correct 474 ms 7800 KB Output is correct
15 Correct 536 ms 7544 KB Output is correct
16 Correct 352 ms 5496 KB Output is correct
17 Correct 512 ms 7672 KB Output is correct
18 Correct 469 ms 7160 KB Output is correct
19 Correct 1060 ms 13176 KB Output is correct
20 Correct 1763 ms 5112 KB Output is correct
21 Correct 332 ms 992 KB Output is correct
22 Correct 2121 ms 7044 KB Output is correct
23 Correct 227 ms 14072 KB Output is correct
24 Correct 814 ms 9080 KB Output is correct
25 Correct 1394 ms 14504 KB Output is correct
26 Correct 1183 ms 14584 KB Output is correct
27 Correct 1097 ms 13964 KB Output is correct
28 Correct 827 ms 189048 KB Output is correct
29 Correct 1979 ms 210168 KB Output is correct
30 Correct 6157 ms 152952 KB Output is correct
31 Correct 5918 ms 117240 KB Output is correct
32 Correct 551 ms 1144 KB Output is correct
33 Correct 719 ms 3324 KB Output is correct
34 Correct 516 ms 207284 KB Output is correct
35 Correct 1341 ms 105464 KB Output is correct
36 Correct 2522 ms 207992 KB Output is correct
37 Correct 2074 ms 207992 KB Output is correct
38 Correct 2041 ms 207228 KB Output is correct
39 Runtime error 698 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -