oj.uz

Submission #308073

# Submission time Handle Problem Language Result Execution time Memory
308073 2020-09-30T02:44:18 Z daniel920712 Game (IOI13_game) C++14
63 / 100
 1950 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[10000005];
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 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 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 599 ms 12656 KB Output is correct
5 Correct 474 ms 13048 KB Output is correct
6 Correct 502 ms 9976 KB Output is correct
7 Correct 584 ms 9720 KB Output is correct
8 Correct 369 ms 6776 KB Output is correct
9 Correct 538 ms 9720 KB Output is correct
10 Correct 511 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 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 1022 ms 15940 KB Output is correct
13 Correct 1630 ms 6316 KB Output is correct
14 Correct 322 ms 1200 KB Output is correct
15 Correct 1906 ms 8936 KB Output is correct
16 Correct 225 ms 18296 KB Output is correct
17 Correct 853 ms 11512 KB Output is correct
18 Correct 1493 ms 18680 KB Output is correct
19 Correct 1255 ms 18936 KB Output is correct
20 Correct 1213 ms 18424 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 603 ms 12792 KB Output is correct
13 Correct 466 ms 13176 KB Output is correct
14 Correct 501 ms 9848 KB Output is correct
15 Correct 585 ms 9592 KB Output is correct
16 Correct 377 ms 6776 KB Output is correct
17 Correct 552 ms 9848 KB Output is correct
18 Correct 524 ms 9508 KB Output is correct
19 Correct 1020 ms 16120 KB Output is correct
20 Correct 1620 ms 6392 KB Output is correct
21 Correct 311 ms 1144 KB Output is correct
22 Correct 1905 ms 8828 KB Output is correct
23 Correct 224 ms 18296 KB Output is correct
24 Correct 862 ms 11640 KB Output is correct
25 Correct 1470 ms 18552 KB Output is correct
26 Correct 1282 ms 18872 KB Output is correct
27 Correct 1208 ms 18168 KB Output is correct
28 Correct 884 ms 256000 KB Output is correct
29 Runtime error 1871 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 384 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 599 ms 12664 KB Output is correct
13 Correct 467 ms 12976 KB Output is correct
14 Correct 493 ms 9976 KB Output is correct
15 Correct 560 ms 9592 KB Output is correct
16 Correct 379 ms 6688 KB Output is correct
17 Correct 545 ms 9976 KB Output is correct
18 Correct 511 ms 9464 KB Output is correct
19 Correct 1014 ms 15820 KB Output is correct
20 Correct 1622 ms 6392 KB Output is correct
21 Correct 312 ms 1144 KB Output is correct
22 Correct 1950 ms 8908 KB Output is correct
23 Correct 232 ms 18296 KB Output is correct
24 Correct 859 ms 11584 KB Output is correct
25 Correct 1493 ms 18808 KB Output is correct
26 Correct 1277 ms 19088 KB Output is correct
27 Correct 1163 ms 18168 KB Output is correct
28 Correct 881 ms 256000 KB Output is correct
29 Runtime error 1838 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -