oj.uz

Submission #308067

# Submission time Handle Problem Language Result Execution time Memory
308067 2020-09-30T02:36:48 Z daniel920712 Game (IOI13_game) C++14
63 / 100
 2095 ms 193784 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[2000005];
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;
    //printf("%lld %lld %lld\n",here,l,r);
    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);
        //printf("%d %d %d\n",Node[here].l,Node[here].r,Node[here].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:179:21: warning: unused variable 'i' [-Wunused-variable]
  179 |     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:55:14: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |         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 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 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 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 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 636 ms 17084 KB Output is correct
5 Correct 501 ms 17272 KB Output is correct
6 Correct 545 ms 14328 KB Output is correct
7 Correct 638 ms 13816 KB Output is correct
8 Correct 397 ms 9080 KB Output is correct
9 Correct 604 ms 13944 KB Output is correct
10 Correct 568 ms 13564 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 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 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1077 ms 23936 KB Output is correct
13 Correct 1700 ms 12780 KB Output is correct
14 Correct 329 ms 5752 KB Output is correct
15 Correct 2013 ms 17192 KB Output is correct
16 Correct 247 ms 31216 KB Output is correct
17 Correct 973 ms 21368 KB Output is correct
18 Correct 1755 ms 32816 KB Output is correct
19 Correct 1461 ms 32760 KB Output is correct
20 Correct 1392 ms 32212 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 320 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 651 ms 16896 KB Output is correct
13 Correct 499 ms 17144 KB Output is correct
14 Correct 542 ms 14072 KB Output is correct
15 Correct 667 ms 13952 KB Output is correct
16 Correct 437 ms 9080 KB Output is correct
17 Correct 640 ms 14200 KB Output is correct
18 Correct 604 ms 13504 KB Output is correct
19 Correct 1123 ms 23932 KB Output is correct
20 Correct 1771 ms 12792 KB Output is correct
21 Correct 335 ms 5824 KB Output is correct
22 Correct 2095 ms 17016 KB Output is correct
23 Correct 253 ms 31224 KB Output is correct
24 Correct 1045 ms 21320 KB Output is correct
25 Correct 1838 ms 32560 KB Output is correct
26 Correct 1601 ms 32736 KB Output is correct
27 Correct 1477 ms 32140 KB Output is correct
28 Runtime error 297 ms 193784 KB Execution killed with signal 11 (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 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 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 648 ms 16888 KB Output is correct
13 Correct 495 ms 17144 KB Output is correct
14 Correct 547 ms 14072 KB Output is correct
15 Correct 639 ms 13820 KB Output is correct
16 Correct 410 ms 9212 KB Output is correct
17 Correct 627 ms 14200 KB Output is correct
18 Correct 587 ms 13688 KB Output is correct
19 Correct 1072 ms 24184 KB Output is correct
20 Correct 1702 ms 12972 KB Output is correct
21 Correct 326 ms 5752 KB Output is correct
22 Correct 2012 ms 17272 KB Output is correct
23 Correct 246 ms 31096 KB Output is correct
24 Correct 1010 ms 21368 KB Output is correct
25 Correct 1747 ms 32632 KB Output is correct
26 Correct 1471 ms 32760 KB Output is correct
27 Correct 1402 ms 32120 KB Output is correct
28 Runtime error 303 ms 193528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -