Submission #587198

#	Time	Username	Problem	Language	Result	Execution time	Memory
587198		yutabi	Game (IOI13_game)	C++14	0 / 100	2 ms	468 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 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(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);
            }
        }

        currx->val=currx->Y->val;

        if(Lx==Rx)
        {
            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;
        }
    }


}

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<=U)
        {
            if(curry->R!=0)
            {
                processy.pb(make_pair(curry->R,ii(My+1,Ry)));
            }
        }
    }

    return ans;
}

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