oj.uz

답안 #88506

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
88506 2018-12-06T08:45:19 Z gs18115 게임 (IOI13_game) C++14
10 / 100
 1152 ms 15264 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;
        }
        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:214: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:305: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:338: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:367:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=L+R>>1;
                 ~^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 544 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 2 ms 544 KB Output is correct
9 Correct 2 ms 664 KB Output is correct
10 Correct 1 ms 664 KB Output is correct
11 Correct 2 ms 664 KB Output is correct
12 Correct 2 ms 664 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 664 KB Output is correct
2 Correct 2 ms 664 KB Output is correct
3 Correct 3 ms 664 KB Output is correct
4 Correct 759 ms 10700 KB Output is correct
5 Correct 464 ms 10836 KB Output is correct
6 Incorrect 768 ms 10836 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10836 KB Output is correct
2 Correct 3 ms 10836 KB Output is correct
3 Correct 3 ms 10836 KB Output is correct
4 Correct 2 ms 10836 KB Output is correct
5 Correct 2 ms 10836 KB Output is correct
6 Correct 2 ms 10836 KB Output is correct
7 Correct 2 ms 10836 KB Output is correct
8 Correct 3 ms 10836 KB Output is correct
9 Correct 2 ms 10836 KB Output is correct
10 Correct 2 ms 10836 KB Output is correct
11 Correct 3 ms 10836 KB Output is correct
12 Incorrect 1152 ms 15264 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 15264 KB Output is correct
2 Correct 3 ms 15264 KB Output is correct
3 Correct 3 ms 15264 KB Output is correct
4 Correct 2 ms 15264 KB Output is correct
5 Correct 2 ms 15264 KB Output is correct
6 Correct 3 ms 15264 KB Output is correct
7 Correct 2 ms 15264 KB Output is correct
8 Correct 1 ms 15264 KB Output is correct
9 Correct 2 ms 15264 KB Output is correct
10 Correct 2 ms 15264 KB Output is correct
11 Correct 2 ms 15264 KB Output is correct
12 Correct 753 ms 15264 KB Output is correct
13 Correct 462 ms 15264 KB Output is correct
14 Incorrect 795 ms 15264 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15264 KB Output is correct
2 Correct 3 ms 15264 KB Output is correct
3 Correct 3 ms 15264 KB Output is correct
4 Correct 2 ms 15264 KB Output is correct
5 Correct 2 ms 15264 KB Output is correct
6 Correct 3 ms 15264 KB Output is correct
7 Correct 2 ms 15264 KB Output is correct
8 Correct 2 ms 15264 KB Output is correct
9 Correct 3 ms 15264 KB Output is correct
10 Correct 2 ms 15264 KB Output is correct
11 Correct 2 ms 15264 KB Output is correct
12 Correct 762 ms 15264 KB Output is correct
13 Correct 469 ms 15264 KB Output is correct
14 Incorrect 791 ms 15264 KB Output isn't correct
15 Halted 0 ms 0 KB -