oj.uz

Submission #88501

# Submission time Handle Problem Language Result Execution time Memory
88501 2018-12-06T08:09:23 Z gs18115 Game (IOI13_game) C++14
80 / 100
 10307 ms 257024 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()
    {
        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)
        {
            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(!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:37: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:128: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:202: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:293: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:323: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:350: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 628 KB Output is correct
3 Correct 3 ms 628 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 2 ms 628 KB Output is correct
8 Correct 2 ms 628 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 2 ms 716 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 757 ms 10696 KB Output is correct
5 Correct 465 ms 10944 KB Output is correct
6 Correct 753 ms 10944 KB Output is correct
7 Correct 848 ms 10944 KB Output is correct
8 Correct 533 ms 10944 KB Output is correct
9 Correct 851 ms 10944 KB Output is correct
10 Correct 736 ms 12236 KB Output is correct
11 Correct 2 ms 12236 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12236 KB Output is correct
2 Correct 2 ms 12236 KB Output is correct
3 Correct 3 ms 12236 KB Output is correct
4 Correct 2 ms 12236 KB Output is correct
5 Correct 2 ms 12236 KB Output is correct
6 Correct 3 ms 12236 KB Output is correct
7 Correct 2 ms 12236 KB Output is correct
8 Correct 2 ms 12236 KB Output is correct
9 Correct 3 ms 12236 KB Output is correct
10 Correct 2 ms 12236 KB Output is correct
11 Correct 2 ms 12236 KB Output is correct
12 Correct 1176 ms 24768 KB Output is correct
13 Correct 2741 ms 24768 KB Output is correct
14 Correct 379 ms 24768 KB Output is correct
15 Correct 3229 ms 24768 KB Output is correct
16 Correct 257 ms 25384 KB Output is correct
17 Correct 1526 ms 25384 KB Output is correct
18 Correct 2868 ms 25656 KB Output is correct
19 Correct 2313 ms 25872 KB Output is correct
20 Correct 2126 ms 25872 KB Output is correct
21 Correct 2 ms 25872 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 25872 KB Output is correct
2 Correct 3 ms 25872 KB Output is correct
3 Correct 3 ms 25872 KB Output is correct
4 Correct 2 ms 25872 KB Output is correct
5 Correct 2 ms 25872 KB Output is correct
6 Correct 2 ms 25872 KB Output is correct
7 Correct 2 ms 25872 KB Output is correct
8 Correct 2 ms 25872 KB Output is correct
9 Correct 2 ms 25872 KB Output is correct
10 Correct 2 ms 25872 KB Output is correct
11 Correct 0 ms 25872 KB Output is correct
12 Correct 736 ms 25872 KB Output is correct
13 Correct 460 ms 25872 KB Output is correct
14 Correct 775 ms 25872 KB Output is correct
15 Correct 893 ms 25872 KB Output is correct
16 Correct 571 ms 25872 KB Output is correct
17 Correct 910 ms 25872 KB Output is correct
18 Correct 734 ms 25872 KB Output is correct
19 Correct 1177 ms 25872 KB Output is correct
20 Correct 2777 ms 25872 KB Output is correct
21 Correct 380 ms 25872 KB Output is correct
22 Correct 3214 ms 25872 KB Output is correct
23 Correct 262 ms 25872 KB Output is correct
24 Correct 1594 ms 25872 KB Output is correct
25 Correct 2867 ms 25872 KB Output is correct
26 Correct 2314 ms 25872 KB Output is correct
27 Correct 2087 ms 25872 KB Output is correct
28 Correct 915 ms 77448 KB Output is correct
29 Correct 2177 ms 77448 KB Output is correct
30 Correct 7730 ms 113128 KB Output is correct
31 Correct 7221 ms 113128 KB Output is correct
32 Correct 687 ms 113128 KB Output is correct
33 Correct 1040 ms 113128 KB Output is correct
34 Correct 385 ms 113128 KB Output is correct
35 Correct 2106 ms 113128 KB Output is correct
36 Correct 4217 ms 113128 KB Output is correct
37 Correct 3167 ms 113128 KB Output is correct
38 Correct 2893 ms 113128 KB Output is correct
39 Correct 2435 ms 113128 KB Output is correct
40 Correct 2 ms 113128 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 113128 KB Output is correct
2 Correct 3 ms 113128 KB Output is correct
3 Correct 3 ms 113128 KB Output is correct
4 Correct 2 ms 113128 KB Output is correct
5 Correct 2 ms 113128 KB Output is correct
6 Correct 3 ms 113128 KB Output is correct
7 Correct 1 ms 113128 KB Output is correct
8 Correct 2 ms 113128 KB Output is correct
9 Correct 2 ms 113128 KB Output is correct
10 Correct 2 ms 113128 KB Output is correct
11 Correct 2 ms 113128 KB Output is correct
12 Correct 742 ms 113128 KB Output is correct
13 Correct 466 ms 113128 KB Output is correct
14 Correct 781 ms 113128 KB Output is correct
15 Correct 936 ms 113128 KB Output is correct
16 Correct 561 ms 113128 KB Output is correct
17 Correct 902 ms 113128 KB Output is correct
18 Correct 779 ms 113128 KB Output is correct
19 Correct 1186 ms 113128 KB Output is correct
20 Correct 2771 ms 113128 KB Output is correct
21 Correct 382 ms 113128 KB Output is correct
22 Correct 3254 ms 113128 KB Output is correct
23 Correct 249 ms 113128 KB Output is correct
24 Correct 1516 ms 113128 KB Output is correct
25 Correct 2729 ms 113128 KB Output is correct
26 Correct 2421 ms 113128 KB Output is correct
27 Correct 2157 ms 113128 KB Output is correct
28 Correct 938 ms 113128 KB Output is correct
29 Correct 2176 ms 113128 KB Output is correct
30 Correct 7717 ms 116172 KB Output is correct
31 Correct 7203 ms 116172 KB Output is correct
32 Correct 677 ms 116172 KB Output is correct
33 Correct 993 ms 116172 KB Output is correct
34 Correct 372 ms 116172 KB Output is correct
35 Correct 1959 ms 116172 KB Output is correct
36 Correct 3658 ms 116172 KB Output is correct
37 Correct 2907 ms 116172 KB Output is correct
38 Correct 3113 ms 116172 KB Output is correct
39 Correct 1366 ms 181828 KB Output is correct
40 Correct 3544 ms 181828 KB Output is correct
41 Runtime error 10307 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
42 Halted 0 ms 0 KB -