제출 #1303634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303634		activedeltorre	게임 (IOI13_game)	C++20	10 / 100	1637 ms	21580 KiB

game

#include "game.h"
#include<map>
#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;
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++)
        {
            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) {
    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;
    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: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20