oj.uz

Submission #308075

# Submission time Handle Problem Language Result Execution time Memory
308075 2020-09-30T02:47:00 Z daniel920712 Game (IOI13_game) C++14
63 / 100
 1916 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 l,r;
    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].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(int here,int l,int r,int 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(int x,int y,long long con,int 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(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(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(int, int, int, int)':
game.cpp:67:14: warning: 'll' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |         Merge(Node[here].nxr,ll,rr,what);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
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 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 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 605 ms 12740 KB Output is correct
5 Correct 468 ms 13048 KB Output is correct
6 Correct 505 ms 9976 KB Output is correct
7 Correct 577 ms 9916 KB Output is correct
8 Correct 377 ms 6648 KB Output is correct
9 Correct 556 ms 9852 KB Output is correct
10 Correct 531 ms 9336 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 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 1 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 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 1029 ms 15968 KB Output is correct
13 Correct 1630 ms 6392 KB Output is correct
14 Correct 316 ms 992 KB Output is correct
15 Correct 1916 ms 8952 KB Output is correct
16 Correct 228 ms 18424 KB Output is correct
17 Correct 851 ms 11640 KB Output is correct
18 Correct 1512 ms 18808 KB Output is correct
19 Correct 1258 ms 18904 KB Output is correct
20 Correct 1265 ms 18296 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 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 0 ms 384 KB Output is correct
12 Correct 594 ms 12664 KB Output is correct
13 Correct 467 ms 12924 KB Output is correct
14 Correct 488 ms 9976 KB Output is correct
15 Correct 583 ms 9720 KB Output is correct
16 Correct 379 ms 6728 KB Output is correct
17 Correct 555 ms 9720 KB Output is correct
18 Correct 523 ms 9336 KB Output is correct
19 Correct 1018 ms 15996 KB Output is correct
20 Correct 1628 ms 6316 KB Output is correct
21 Correct 317 ms 1016 KB Output is correct
22 Correct 1910 ms 8936 KB Output is correct
23 Correct 230 ms 18300 KB Output is correct
24 Correct 880 ms 11640 KB Output is correct
25 Correct 1545 ms 18680 KB Output is correct
26 Correct 1252 ms 18936 KB Output is correct
27 Correct 1177 ms 18160 KB Output is correct
28 Correct 872 ms 254716 KB Output is correct
29 Runtime error 1819 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 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 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 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 593 ms 12792 KB Output is correct
13 Correct 463 ms 13048 KB Output is correct
14 Correct 496 ms 10104 KB Output is correct
15 Correct 574 ms 9720 KB Output is correct
16 Correct 367 ms 6648 KB Output is correct
17 Correct 548 ms 9720 KB Output is correct
18 Correct 505 ms 9428 KB Output is correct
19 Correct 1018 ms 16008 KB Output is correct
20 Correct 1627 ms 6136 KB Output is correct
21 Correct 318 ms 1016 KB Output is correct
22 Correct 1912 ms 8824 KB Output is correct
23 Correct 231 ms 18312 KB Output is correct
24 Correct 852 ms 11640 KB Output is correct
25 Correct 1479 ms 18548 KB Output is correct
26 Correct 1244 ms 18804 KB Output is correct
27 Correct 1198 ms 18116 KB Output is correct
28 Correct 878 ms 254840 KB Output is correct
29 Runtime error 1828 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -