oj.uz

Submission #88508

# Submission time Handle Problem Language Result Execution time Memory
88508 2018-12-06T08:48:28 Z gs18115 Game (IOI13_game) C++14
10 / 100
 1165 ms 15296 KB 
#include "game.h"
#include<iostream>
using namespace std;
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;
            }
            flag=false;
            if(Y>mid)
            {
                r=new SY();
                r->update(Y,val);
            }
            else
            {
                l=new SY();
                l->update(Y,val);
            }
            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);
            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:40: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:131: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:204: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:295: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:328: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:357: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 376 KB Output is correct
2 Correct 3 ms 636 KB Output is correct
3 Correct 3 ms 636 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 2 ms 636 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 2 ms 636 KB Output is correct
10 Correct 2 ms 636 KB Output is correct
11 Correct 2 ms 636 KB Output is correct
12 Correct 2 ms 636 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 761 ms 10680 KB Output is correct
5 Correct 470 ms 10956 KB Output is correct
6 Incorrect 784 ms 10956 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10956 KB Output is correct
2 Correct 3 ms 10956 KB Output is correct
3 Correct 3 ms 10956 KB Output is correct
4 Correct 2 ms 10956 KB Output is correct
5 Correct 2 ms 10956 KB Output is correct
6 Correct 3 ms 10956 KB Output is correct
7 Correct 2 ms 10956 KB Output is correct
8 Correct 2 ms 10956 KB Output is correct
9 Correct 2 ms 10956 KB Output is correct
10 Correct 2 ms 10956 KB Output is correct
11 Correct 2 ms 10956 KB Output is correct
12 Incorrect 1165 ms 15296 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15296 KB Output is correct
2 Correct 3 ms 15296 KB Output is correct
3 Correct 3 ms 15296 KB Output is correct
4 Correct 2 ms 15296 KB Output is correct
5 Correct 2 ms 15296 KB Output is correct
6 Correct 2 ms 15296 KB Output is correct
7 Correct 2 ms 15296 KB Output is correct
8 Correct 2 ms 15296 KB Output is correct
9 Correct 2 ms 15296 KB Output is correct
10 Correct 2 ms 15296 KB Output is correct
11 Correct 2 ms 15296 KB Output is correct
12 Correct 752 ms 15296 KB Output is correct
13 Correct 462 ms 15296 KB Output is correct
14 Incorrect 758 ms 15296 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15296 KB Output is correct
2 Correct 3 ms 15296 KB Output is correct
3 Correct 3 ms 15296 KB Output is correct
4 Correct 2 ms 15296 KB Output is correct
5 Correct 2 ms 15296 KB Output is correct
6 Correct 2 ms 15296 KB Output is correct
7 Correct 2 ms 15296 KB Output is correct
8 Correct 2 ms 15296 KB Output is correct
9 Correct 2 ms 15296 KB Output is correct
10 Correct 2 ms 15296 KB Output is correct
11 Correct 2 ms 15296 KB Output is correct
12 Correct 763 ms 15296 KB Output is correct
13 Correct 466 ms 15296 KB Output is correct
14 Incorrect 796 ms 15296 KB Output isn't correct
15 Halted 0 ms 0 KB -