oj.uz

Submission #88509

# Submission time Handle Problem Language Result Execution time Memory
88509 2018-12-06T08:51:08 Z gs18115 Game (IOI13_game) C++14
100 / 100
 9466 ms 176052 KB 
#include "game.h"
typedef long long LL;
LL gcd2(LL X, LL Y) {
    LL tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct SY
{
    bool flag;
    int Y;
    SY*l,*r;
    LL val;
    SY()
    {
        Y=-1;
        flag=true;
        val=0;
        l=r=nullptr;
    }
    inline void update(int y,LL p)
    {
        Y=y;
        val=p;
        return;
    }
    void update(int L,int R,int y,LL p)
    {
        if(L==R)
        {
            val=p;
            return;
        }
        int mid=L+R>>1;
        if(flag)
        {
            if(Y==y)
            {
                val=p;
                return;
            }
            if(Y>mid)
            {
                r=new SY();
                r->update(Y,val);
            }
            else
            {
                l=new SY();
                l->update(Y,val);
            }
            flag=false;
            if(y>mid)
            {
                if(!r)
                {
                    r=new SY();
                    r->update(y,p);
                }
                else
                    r->update(mid+1,R,y,p);
            }
            else
            {
                if(!l)
                {
                    l=new SY();
                    l->update(y,p);
                }
                else
                    l->update(L,mid,y,p);
            }
            LL LP,RP;
            if(!l)
                LP=0;
            else
                LP=l->val;
            if(!r)
                RP=0;
            else
                RP=r->val;
            val=gcd2(LP,RP);
            return;
        }
        if(y>mid)
        {
            if(!r)
            {
                r=new SY();
                r->update(y,p);
            }
            else
                r->update(mid+1,R,y,p);
        }
        else
        {
            if(!l)
            {
                l=new SY();
                l->update(y,p);
            }
            else
                l->update(L,mid,y,p);
        }
        LL LP,RP;
        if(!l)
            LP=0;
        else
            LP=l->val;
        if(!r)
            RP=0;
        else
            RP=r->val;
        val=gcd2(LP,RP);
        return;
    }
    void update(SY*P,int L,int R,int y,LL p)
    {
        if(L==R)
        {
            val=P->val;
            Y=P->Y;
            return;
        }
        int mid=L+R>>1;
        if(!flag&&P->flag)
        {
            P->flag=false;
            if(P->Y>mid)
            {
                P->r=new SY();
                P->r->update(P->Y,P->val);
            }
            else
            {
                P->l=new SY();
                P->l->update(P->Y,P->val);
            }
        }
        else if(flag&&!P->flag)
        {
            flag=false;
            if(Y>mid)
            {
                r=new SY();
                r->update(Y,val);
            }
            else
            {
                l=new SY();
                l->update(Y,val);
            }
        }
        val=P->val;
        Y=P->Y;
        if(flag)
            return;
        if(y>mid)
        {
            if(!P->r)
                return;
            else if(!r)
            {
                r=new SY();
                r->update(y,p);
            }
            else
                r->update(P->r,mid+1,R,y,p);
        }
        else
        {
            if(!P->l)
                return;
            else if(!l)
            {
                l=new SY();
                l->update(y,p);
            }
            else
                l->update(P->l,L,mid,y,p);
        }
        return;
    }
    void update(SY*Lp,SY*Rp,int L,int R,int y,LL p)
    {
        if(Lp->flag&&Rp->flag&&Lp->Y==Rp->Y)
        {
            Y=Lp->Y;
            val=gcd2(Lp->val,Rp->val);
            flag=true;
            return;
        }
        if(L==R)
        {
            val=gcd2(Lp->val,Rp->val);
            flag=false;
            return;
        }
        int mid=L+R>>1;
        if(flag)
        {
            flag=false;
            if(Y>mid)
            {
                r=new SY();
                r->update(Y,val);
            }
            else
            {
                l=new SY();
                l->update(Y,val);
            }
        }
        if(Lp->flag)
        {
            Lp->flag=false;
            if(Lp->Y>mid)
            {
                Lp->r=new SY();
                Lp->r->update(Lp->Y,Lp->val);
            }
            else
            {
                Lp->l=new SY();
                Lp->l->update(Lp->Y,Lp->val);
            }
        }
        if(Rp->flag)
        {
            Rp->flag=false;
            if(Rp->Y>mid)
            {
                Rp->r=new SY();
                Rp->r->update(Rp->Y,Rp->val);
            }
            else
            {
                Rp->l=new SY();
                Rp->l->update(Rp->Y,Rp->val);
            }
        }
        val=gcd2(Lp->val,Rp->val);
        if(y>mid)
        {
            if(!Lp->r&&!Rp->r)
                return;
            else if(!r)
            {
                r=new SY();
                r->update(y,p);
            }
            else if(!Lp->r)
                r->update(Rp->r,mid+1,R,y,p);
            else if(!Rp->r)
                r->update(Lp->r,mid+1,R,y,p);
            else
                r->update(Lp->r,Rp->r,mid+1,R,y,p);
        }
        else
        {
            if(!Lp->l&&!Rp->l)
                return;
            else if(!l)
            {
                l=new SY();
                l->update(y,p);
            }
            else if(!Lp->l)
                l->update(Rp->l,L,mid,y,p);
            else if(!Rp->l)
                l->update(Lp->l,L,mid,y,p);
            else
                l->update(Lp->l,Rp->l,L,mid,y,p);
        }
        return;
    }
    LL query(int L,int R,int y1,int y2)
    {
        if(L>y2||R<y1)
            return 0;
        if(L>=y1&&R<=y2)
            return val;
        if(flag)
        {
            if(y1<=Y&&Y<=y2)
                return val;
            else
                return 0;
        }
        int mid=L+R>>1;
        LL LP,RP;
        if(!l)
            LP=0;
        else
            LP=l->query(L,mid,y1,y2);
        if(!r)
            RP=0;
        else
            RP=r->query(mid+1,R,y1,y2);
        return gcd2(LP,RP);
    }
};
int R,C;
struct SX
{
    SX*l,*r;
    SY*val;
    SX()
    {
        val=new SY();
        l=r=nullptr;
    }
    void update(int L,int R,int x,int y,LL p)
    {
        if(L==R)
        {
            if(val->Y==-1)
                val->update(y,p);
            else
                val->update(0,C-1,y,p);
            return;
        }
        int mid=L+R>>1;
        if(x>mid)
        {
            if(!r)
                r=new SX();
            r->update(mid+1,R,x,y,p);
        }
        else
        {
            if(!l)
                l=new SX();
            l->update(L,mid,x,y,p);
        }
        if(val->Y==-1)
            val->update(y,p);
        else if(!r)
            val->update(l->val,0,C-1,y,p);
        else if(!l)
            val->update(r->val,0,C-1,y,p);
        else
            val->update(l->val,r->val,0,C-1,y,p);
        return;
    }
    LL query(int L,int R,int x1,int x2,int y1,int y2)
    {
        if(L>x2||R<x1)
            return 0;
        if(L>=x1&&R<=x2)
            return val->query(0,C-1,y1,y2);
        int mid=L+R>>1;
        LL LP,RP;
        if(!l)
            LP=0;
        else
            LP=l->query(L,mid,x1,x2,y1,y2);
        if(!r)
            RP=0;
        else
            RP=r->query(mid+1,R,x1,x2,y1,y2);
        return gcd2(LP,RP);
    }
}*rt;
void init(int R,int C)
{
    ::R=R;
    ::C=C;
    rt=new SX();
    return;
}
void update(int P,int Q,long long K)
{
    rt->update(0,R-1,P,Q,K);
    return;
}
LL calculate(int P,int Q,int U,int V)
{
    return rt->query(0,R-1,P,U,Q,V);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In member function 'void SY::update(int, int, int, LL)':
game.cpp:38:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~
game.cpp: In member function 'void SY::update(SY*, int, int, int, LL)':
game.cpp:129:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~
game.cpp: In member function 'void SY::update(SY*, SY*, int, int, int, LL)':
game.cpp:203:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~
game.cpp: In member function 'LL SY::query(int, int, int, int)':
game.cpp:294:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~
game.cpp: In member function 'void SX::update(int, int, int, int, LL)':
game.cpp:327:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~
game.cpp: In member function 'LL SX::query(int, int, int, int, int, int)':
game.cpp:356:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 372 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 656 KB Output is correct
7 Correct 2 ms 656 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Correct 2 ms 656 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 2 ms 748 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 736 ms 10540 KB Output is correct
5 Correct 448 ms 10872 KB Output is correct
6 Correct 756 ms 10872 KB Output is correct
7 Correct 977 ms 10872 KB Output is correct
8 Correct 539 ms 10872 KB Output is correct
9 Correct 864 ms 10872 KB Output is correct
10 Correct 735 ms 12360 KB Output is correct
11 Correct 2 ms 12360 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12360 KB Output is correct
2 Correct 2 ms 12360 KB Output is correct
3 Correct 2 ms 12360 KB Output is correct
4 Correct 2 ms 12360 KB Output is correct
5 Correct 2 ms 12360 KB Output is correct
6 Correct 2 ms 12360 KB Output is correct
7 Correct 2 ms 12360 KB Output is correct
8 Correct 2 ms 12360 KB Output is correct
9 Correct 2 ms 12360 KB Output is correct
10 Correct 2 ms 12360 KB Output is correct
11 Correct 2 ms 12360 KB Output is correct
12 Correct 1134 ms 20344 KB Output is correct
13 Correct 2818 ms 20344 KB Output is correct
14 Correct 374 ms 20344 KB Output is correct
15 Correct 3236 ms 21816 KB Output is correct
16 Correct 238 ms 27104 KB Output is correct
17 Correct 1345 ms 27104 KB Output is correct
18 Correct 2464 ms 27496 KB Output is correct
19 Correct 2133 ms 27680 KB Output is correct
20 Correct 1961 ms 27680 KB Output is correct
21 Correct 2 ms 27680 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 27680 KB Output is correct
2 Correct 2 ms 27680 KB Output is correct
3 Correct 2 ms 27680 KB Output is correct
4 Correct 2 ms 27680 KB Output is correct
5 Correct 2 ms 27680 KB Output is correct
6 Correct 3 ms 27680 KB Output is correct
7 Correct 2 ms 27680 KB Output is correct
8 Correct 2 ms 27680 KB Output is correct
9 Correct 2 ms 27680 KB Output is correct
10 Correct 2 ms 27680 KB Output is correct
11 Correct 2 ms 27680 KB Output is correct
12 Correct 737 ms 27680 KB Output is correct
13 Correct 452 ms 27680 KB Output is correct
14 Correct 765 ms 27680 KB Output is correct
15 Correct 909 ms 27680 KB Output is correct
16 Correct 540 ms 27680 KB Output is correct
17 Correct 872 ms 27680 KB Output is correct
18 Correct 776 ms 27680 KB Output is correct
19 Correct 1147 ms 27680 KB Output is correct
20 Correct 2803 ms 27680 KB Output is correct
21 Correct 370 ms 27680 KB Output is correct
22 Correct 3278 ms 27680 KB Output is correct
23 Correct 243 ms 27680 KB Output is correct
24 Correct 1409 ms 27680 KB Output is correct
25 Correct 2578 ms 27680 KB Output is correct
26 Correct 2092 ms 27680 KB Output is correct
27 Correct 1929 ms 27680 KB Output is correct
28 Correct 795 ms 56912 KB Output is correct
29 Correct 1905 ms 56912 KB Output is correct
30 Correct 7433 ms 57176 KB Output is correct
31 Correct 7070 ms 57176 KB Output is correct
32 Correct 672 ms 57176 KB Output is correct
33 Correct 962 ms 57176 KB Output is correct
34 Correct 334 ms 57176 KB Output is correct
35 Correct 1720 ms 57176 KB Output is correct
36 Correct 3378 ms 57176 KB Output is correct
37 Correct 2626 ms 60720 KB Output is correct
38 Correct 2708 ms 62492 KB Output is correct
39 Correct 2208 ms 62492 KB Output is correct
40 Correct 2 ms 62492 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 62492 KB Output is correct
2 Correct 2 ms 62492 KB Output is correct
3 Correct 3 ms 62492 KB Output is correct
4 Correct 2 ms 62492 KB Output is correct
5 Correct 2 ms 62492 KB Output is correct
6 Correct 2 ms 62492 KB Output is correct
7 Correct 2 ms 62492 KB Output is correct
8 Correct 2 ms 62492 KB Output is correct
9 Correct 2 ms 62492 KB Output is correct
10 Correct 2 ms 62492 KB Output is correct
11 Correct 2 ms 62492 KB Output is correct
12 Correct 725 ms 62492 KB Output is correct
13 Correct 446 ms 62492 KB Output is correct
14 Correct 790 ms 62492 KB Output is correct
15 Correct 902 ms 62492 KB Output is correct
16 Correct 551 ms 62492 KB Output is correct
17 Correct 835 ms 62492 KB Output is correct
18 Correct 776 ms 62492 KB Output is correct
19 Correct 1154 ms 62492 KB Output is correct
20 Correct 2776 ms 62492 KB Output is correct
21 Correct 376 ms 62492 KB Output is correct
22 Correct 3283 ms 62492 KB Output is correct
23 Correct 238 ms 62492 KB Output is correct
24 Correct 1436 ms 62492 KB Output is correct
25 Correct 2801 ms 62492 KB Output is correct
26 Correct 2276 ms 62492 KB Output is correct
27 Correct 2095 ms 62492 KB Output is correct
28 Correct 858 ms 69980 KB Output is correct
29 Correct 1957 ms 69980 KB Output is correct
30 Correct 7416 ms 70120 KB Output is correct
31 Correct 7117 ms 70120 KB Output is correct
32 Correct 679 ms 70120 KB Output is correct
33 Correct 997 ms 70120 KB Output is correct
34 Correct 348 ms 70120 KB Output is correct
35 Correct 1720 ms 70120 KB Output is correct
36 Correct 3286 ms 70120 KB Output is correct
37 Correct 2566 ms 70120 KB Output is correct
38 Correct 2880 ms 70120 KB Output is correct
39 Correct 1120 ms 126516 KB Output is correct
40 Correct 3170 ms 126516 KB Output is correct
41 Correct 9466 ms 126516 KB Output is correct
42 Correct 8978 ms 126516 KB Output is correct
43 Correct 654 ms 126516 KB Output is correct
44 Correct 847 ms 126516 KB Output is correct
45 Correct 2218 ms 126516 KB Output is correct
46 Correct 4187 ms 154212 KB Output is correct
47 Correct 4476 ms 165336 KB Output is correct
48 Correct 4435 ms 176052 KB Output is correct
49 Correct 2 ms 176052 KB Output is correct