oj.uz

Submission #88507

# Submission time Handle Problem Language Result Execution time Memory
88507 2018-12-06T08:47:01 Z gs18115 Game (IOI13_game) C++14
10 / 100
 1155 ms 15180 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)
        {
            /*if(P->Y>mid)
            {
                if(!r)
                {
                    r=new SY();
                    r->update(P->Y,P->val);
                }
                else
                    r->update(mid+1,R,P->Y,P->val);
            }
            else
            {
                if(!l)
                {
                    l=new SY();
                    l->update(P->Y,P->val);
                }
                else
                    l->update(L,mid,P->Y,P->val);
            }
            return;*/
            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:225: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:316: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:349: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:378: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 3 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 3 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 10572 KB Output is correct
5 Correct 470 ms 10808 KB Output is correct
6 Incorrect 791 ms 10808 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 10808 KB Output is correct
2 Correct 3 ms 10808 KB Output is correct
3 Correct 3 ms 10808 KB Output is correct
4 Correct 2 ms 10808 KB Output is correct
5 Correct 2 ms 10808 KB Output is correct
6 Correct 3 ms 10808 KB Output is correct
7 Correct 2 ms 10808 KB Output is correct
8 Correct 2 ms 10808 KB Output is correct
9 Correct 2 ms 10808 KB Output is correct
10 Correct 2 ms 10808 KB Output is correct
11 Correct 2 ms 10808 KB Output is correct
12 Incorrect 1155 ms 15180 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 15180 KB Output is correct
2 Correct 3 ms 15180 KB Output is correct
3 Correct 2 ms 15180 KB Output is correct
4 Correct 2 ms 15180 KB Output is correct
5 Correct 2 ms 15180 KB Output is correct
6 Correct 2 ms 15180 KB Output is correct
7 Correct 2 ms 15180 KB Output is correct
8 Correct 0 ms 15180 KB Output is correct
9 Correct 2 ms 15180 KB Output is correct
10 Correct 2 ms 15180 KB Output is correct
11 Correct 2 ms 15180 KB Output is correct
12 Correct 752 ms 15180 KB Output is correct
13 Correct 467 ms 15180 KB Output is correct
14 Incorrect 783 ms 15180 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 15180 KB Output is correct
2 Correct 3 ms 15180 KB Output is correct
3 Correct 3 ms 15180 KB Output is correct
4 Correct 2 ms 15180 KB Output is correct
5 Correct 2 ms 15180 KB Output is correct
6 Correct 2 ms 15180 KB Output is correct
7 Correct 2 ms 15180 KB Output is correct
8 Correct 2 ms 15180 KB Output is correct
9 Correct 2 ms 15180 KB Output is correct
10 Correct 2 ms 15180 KB Output is correct
11 Correct 2 ms 15180 KB Output is correct
12 Correct 744 ms 15180 KB Output is correct
13 Correct 464 ms 15180 KB Output is correct
14 Incorrect 799 ms 15180 KB Output isn't correct
15 Halted 0 ms 0 KB -