Submission #587256

#	Time	Username	Problem	Language	Result	Execution time	Memory
587256		yutabi	Game (IOI13_game)	C++14	63 / 100	2677 ms	256000 KiB

game

#include "game.h"

#define gcd gcd2


#include <bits/stdc++.h>
using namespace std;


#define pb push_back


typedef long long ll;
typedef pair <int,int> ii;


long long gcd2(long long X, long long Y)
{
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct nodex;

struct nodey
{
    nodey* L=0;
    nodey* R=0;

    nodey* par=0;

    nodex* parx=0;

    ll val=0;
};

struct nodex
{
    nodex* L=0;
    nodex* R=0;

    nodex* par=0;

    nodey* Y=0;

    ll val=0;
};


int r;
int c;

nodex* segment_tree;

void check()
{
    vector <pair <nodex*,ii> > processx;

    processx.pb(make_pair(segment_tree,ii(0,r-1)));

    while(processx.size())
    {
        nodex* currx=processx.back().first;

        int Lx=processx.back().second.first;
        int Rx=processx.back().second.second;

        processx.pop_back();

        printf("%lld %d %d\n",currx->val,Lx,Rx);

        vector <pair <nodey*,ii> > processy;

        if(currx->Y!=0)
        {
            processy.pb(make_pair(currx->Y,ii(0,c-1)));
        }

        while(processy.size())
        {
            nodey* curry=processy.back().first;

            int Ly=processy.back().second.first;
            int Ry=processy.back().second.second;

            processy.pop_back();

            printf("%lld %d %d\n",curry->val,Ly,Ry);

            if(curry->L!=0)
            {
                processy.pb(make_pair(curry->L,ii(Ly,(Ly+Ry)/2)));
            }

            if(curry->R!=0)
            {
                processy.pb(make_pair(curry->R,ii((Ly+Ry)/2+1,Ry)));
            }
        }

        printf("\n");

        if(currx->L!=0)
        {
            processx.pb(make_pair(currx->L,ii(Lx,(Lx+Rx)/2)));
        }

        if(currx->R!=0)
        {
            processx.pb(make_pair(currx->R,ii((Lx+Rx)/2+1,Rx)));
        }
    }

    printf("\n");
}

void init(int R, int C)
{
    r=R;
    c=C;

    segment_tree=new nodex;
}

void update(int P, int Q, long long K)
{
    nodex* currx=segment_tree;

    int Lx=0;
    int Rx=r-1;

    while(1)
    {
        if(Lx==Rx)
        {
            if(currx->Y==0)
            {
                currx->Y=new nodey;
                 
                currx->Y->parx=currx;
            }

            nodey* curry=currx->Y;

            int Ly=0;
            int Ry=c-1;

            while(1)
            {
                if(Ly==Ry)
                {
                    curry->val=K;

                    break;
                }

                int My=(Ly+Ry)/2;

                if(Q<=My)
                {
                    if(curry->L==0)
                    {
                        curry->L=new nodey;
                        curry->L->par=curry;
                    }

                    curry=curry->L;

                    Ry=My;
                }

                else
                {
                    if(curry->R==0)
                    {
                        curry->R=new nodey;
                        curry->R->par=curry;
                    }

                    curry=curry->R;

                    Ly=My+1;
                }
            }

            while(1)
            {
                if(curry->par==0)
                {
                    break;
                }

                curry=curry->par;

                curry->val=0;

                if(curry->L!=0)
                {
                    curry->val=curry->L->val;
                }

                if(curry->R!=0)
                {
                    curry->val=gcd(curry->val,curry->R->val);
                }
            }

            break;
        }

        int Mx=(Lx+Rx)/2;

        if(P<=Mx)
        {
            if(currx->L==0)
            {
                currx->L=new nodex;
                currx->L->par=currx;
            }

            currx=currx->L;

            Rx=Mx;
        }

        else
        {
            if(currx->R==0)
            {
                currx->R=new nodex;
                currx->R->par=currx;
            }

            currx=currx->R;

            Lx=Mx+1;
        }
    }

    while(currx->par!=0)
    {
        currx=currx->par;

        nodex* lx=currx->L;
        nodex* rx=currx->R;

        nodey* curry;

        nodey* ly=0;
        nodey* ry=0;

        if(currx->Y==0)
        {
            currx->Y=new nodey;
            currx->Y->parx=currx;
        }

        curry=currx->Y;

        if(lx!=0)
        {
            ly=lx->Y;
        }

        if(rx!=0)
        {
            ry=rx->Y;
        }

        int Ly=0;
        int Ry=c-1;

        while(1)
        {
            ll ans=0;

            if(ly!=0)
            {
                ans=ly->val;
            }

            if(ry!=0)
            {
                ans=gcd(ans,ry->val);
            }

            if(curry!=0)
            {
                curry->val=ans;
            }

            if(Ly==Ry)
            {
                break;
            }

            int My=(Ly+Ry)/2;

            if(Q<=My)
            {
                if(curry->L==0)
                {
                    curry->L=new nodey;
                    curry->L->par=curry;
                }

                curry=curry->L;
                
                if(ly!=0)
                {
                    ly=ly->L;
                }
                
                if(ry!=0)
                {
                    ry=ry->L;
                }

                Ry=My;
            }

            else
            {
                if(curry->R==0)
                {
                    curry->R=new nodey;
                    curry->R->par=curry;
                }

                curry=curry->R;
                
                if(ly!=0)
                {
                    ly=ly->R;
                }
                
                if(ry!=0)
                {
                    ry=ry->R;
                }

                Ly=My+1;
            }
        }
    }

    //check();
}

long long calculate(int P, int Q, int U, int V)
{
    ll ans=0;

    vector <pair <nodex*,ii> > processx;
    vector <pair <nodey*,ii> > processy;

    processx.pb(make_pair(segment_tree,ii(0,r-1)));

    while(processx.size())
    {
        nodex* currx=processx.back().first;

        int Lx=processx.back().second.first;
        int Rx=processx.back().second.second;

        processx.pop_back();

        int Mx=(Lx+Rx)/2;

        if(P<=Lx && Rx<=U)
        {
            if(currx->Y!=0)
            {
                processy.pb(make_pair(currx->Y,ii(0,c-1)));
            }

            continue;
        }

        if(P<=Mx)
        {
            if(currx->L!=0)
            {
                processx.pb(make_pair(currx->L,ii(Lx,Mx)));
            }
        }

        if(Mx+1<=U)
        {
            if(currx->R!=0)
            {
                processx.pb(make_pair(currx->R,ii(Mx+1,Rx)));
            }
        }
    }

    while(processy.size())
    {
        nodey* curry=processy.back().first;

        int Ly=processy.back().second.first;
        int Ry=processy.back().second.second;

        processy.pop_back();

        int My=(Ly+Ry)/2;

        if(Q<=Ly && Ry<=V)
        {
            ans=gcd(ans,curry->val);
            continue;
        }

        if(Q<=My)
        {
            if(curry->L!=0)
            {
                processy.pb(make_pair(curry->L,ii(Ly,My)));
            }
        }

        if(My+1<=V)
        {
            if(curry->R!=0)
            {
                processy.pb(make_pair(curry->R,ii(My+1,Ry)));
            }
        }
    }

    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20