Submission #1303644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303644		activedeltorre	Game (IOI13_game)	C++20	80 / 100	2856 ms	37892 KiB

game

#include "game.h"
#include<map>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
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 ura
{
    int a,b;
    long long value;
};
map<pair<int,int>,int>mp;
map<pair<int,int>,long long>realval;
int ids=0;
int invector[25000];
int buc[25000];
vector<ura>elem[205];
int top[205];
int bot[205];
vector<ura>pset;
vector<ura>nset;
int bucket=100;
int buckets;
int cb(int index,int value)
{
    int st=0,dr=elem[index].size()-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(elem[index][mij].b>=value)
        {
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    return dr+1;
}
long long dp[205][205][205];
long long find(int index,int left,int right)
{
    int i1=cb(index,left);
    int i2=cb(index,right+1)-1;
    if(i1<=i2)
    {
        return dp[index][i1][i2];
    }
    return 0;
}
void recalcbucket(int index)
{
    for(int i=0; i<elem[index].size(); i++)
    {
        dp[index][i][i]=elem[index][i].value;
        for(int j=i+1; j<elem[index].size(); j++)
        {
            dp[index][i][j]=gcd2(dp[index][i][j-1],elem[index][j].value);
        }
    }
}
void recalcvalue(int index,int a,int b,long long val)
{
    for(int i=0; i<elem[index].size(); i++)
    {
        if(elem[index][i].a==a && elem[index][i].b==b)
        {
            elem[index][i].value=val;
        }
    }
    recalcbucket(index);
}
void init(int R, int C)
{
    buckets=0;
}
bool cmp(ura a,ura b)
{
    return a.a<b.a;
}
bool cmp2(ura a,ura b)
{
    return a.b<b.b;
}
void resetbuckets()
{
    for(auto x:nset)
    {
        pset.push_back(x);
    }
    nset.clear();
    sort(pset.begin(),pset.end(),cmp);
    for(int i=1; i<=ids; i++)
    {
        invector[i]=1;
    }
    int cnt=0;
    for(int z=0; z<pset.size()/bucket; z++)
    {
        elem[z].clear();
        top[z]=1100000000;
        bot[z]=0;
        for(int i=0; i<bucket; i++)
        {
            pset[cnt].value=realval[{pset[cnt].a,pset[cnt].b}];
            elem[z].push_back(pset[cnt]);
            top[z]=min(top[z],pset[cnt].a);
            bot[z]=max(bot[z],pset[cnt].a);
            buc[mp[ {pset[cnt].a,pset[cnt].b}]]=z;
            cnt++;
        }
        sort(elem[z].begin(),elem[z].end(),cmp2);
        recalcbucket(z);
    }
    buckets=pset.size()/bucket;
}
void update(int P, int Q, long long K)
{
    realval[{P,Q}]=K;
    if(mp[ {P,Q}]==0)
    {
        ids++;
        mp[ {P,Q}]=ids;
        invector[ids]=0;
        nset.push_back({P,Q,K});
        if(nset.size()==bucket)
        {
            resetbuckets();
        }
    }
    else
    {
        if(invector[mp[ {P,Q}]]==1)
        {
            recalcvalue(buc[mp[ {P,Q}]],P,Q,K);
        }
        else
        {
            for(int i=0; i<nset.size(); i++)
            {
                if(P==nset[i].a && Q==nset[i].b)
                {
                    nset[i].value=K;
                }
            }
        }
    }
}
long long calculate(int P, int Q, int U, int V)
{
    long long rez=0;
    long long rez2=0;
    /*
    for(int i=0; i<nset2.size(); i++)
    {
        if(P<=nset2[i].a && nset2[i].a<=U && Q<=nset2[i].b && nset2[i].b<=V)
            rez2=gcd2(rez2,nset2[i].value);
    }*/
    for(int i=0; i<nset.size(); i++)
    {
        if(P<=nset[i].a && nset[i].a<=U && Q<=nset[i].b && nset[i].b<=V)
            rez=gcd2(rez,nset[i].value);
    }
    for(int i=0; i<buckets; i++)
    {
        if(P<=top[i] && bot[i]<=U)
        {
            rez=gcd2(rez,find(i,Q,V));
        }
        else if(P<=bot[i] || U>=top[i])
        {
            for(int j=0; j<elem[i].size(); j++)
            {
                if(P<=elem[i][j].a && elem[i][j].a<=U && Q<=elem[i][j].b && elem[i][j].b<=V)
                {
                    rez=gcd2(rez,elem[i][j].value);
                }
            }

        }
    }
    return rez;
}

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