제출 #1286326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286326		HoriaHaivas	게임 (IOI13_game)	C++20	80 / 100	3183 ms	176120 KiB

game

#include<bits/stdc++.h>
#include "game.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

const int lim=1e9;
map<signed,signed> mp;
signed cnt;

struct Node
{
    signed lson;
    signed rson;
    int gcd;
};

Node emptyNode= {0,0,0};

class AINT_aux
{
public:
    signed sz;
    vector<Node> aint;

    void init()///de preferat apeleaza asta
    {
        sz=0;
        aint.clear();
        aint.push_back(emptyNode);
    }

    void update(int l, int r, int val, int poz, int x)
    {
        if (l==r)
        {
            aint[val].gcd=x;///asta e aintu auxiliar
            return;
        }
        int mid;
        mid=(l+r)/2;
        if (poz<=mid)
        {
            if (aint[val].lson==0)
            {
                sz++;
                aint[val].lson=sz;
                aint.push_back(emptyNode); //aint[sz]=emptyNode;
            }
            update(l,mid,aint[val].lson,poz,x);
        }
        else
        {
            if (aint[val].rson==0)
            {
                sz++;
                aint[val].rson=sz;
                aint.push_back(emptyNode); //aint[sz]=emptyNode;
            }
            update(mid+1,r,aint[val].rson,poz,x);
        }
        aint[val].gcd=0;
        if (aint[val].lson!=0)
            aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].lson].gcd);
        if (aint[val].rson!=0)
            aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].rson].gcd);
    }

    int query(int l, int r, int val, int qa, int qb)
    {
        if (qa<=l && r<=qb)
        {
            return aint[val].gcd;
        }
        int mid,ans;
        mid=(l+r)/2;
        ans=0;
        if (qa<=mid)
        {
            if (aint[val].lson!=0)
                ans=__gcd(ans,query(l,mid,aint[val].lson,qa,qb));
        }
        if (qb>mid)
        {
            if (aint[val].rson!=0)
                ans=__gcd(ans,query(mid+1,r,aint[val].rson,qa,qb));
        }
        return ans;
    }

} ainta[23000];

class AINT
{
public:
    signed sz;
    vector<Node> aint;

    void init()///de preferat apeleaza asta
    {
        sz=0;
        aint.clear();
        aint.push_back(emptyNode);
    }

    void update(int l, int r, int val, int poz, int x, int l1, int l2)
    {
        if (l==r)
        {
            aint[val].gcd=ainta[mp[poz]].query(0,lim,0,l1,l2);
            return;
        }
        int mid;
        mid=(l+r)/2;
        if (poz<=mid)
        {
            if (aint[val].lson==0)
            {
                sz++;
                aint[val].lson=sz;
                aint.push_back(emptyNode); //aint[sz]=emptyNode;
            }
            update(l,mid,aint[val].lson,poz,x,l1,l2);
        }
        else
        {
            if (aint[val].rson==0)
            {
                sz++;
                aint[val].rson=sz;
                aint.push_back(emptyNode); //aint[sz]=emptyNode;
            }
            update(mid+1,r,aint[val].rson,poz,x,l1,l2);
        }
        aint[val].gcd=0;
        if (aint[val].lson!=0)
            aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].lson].gcd);
        if (aint[val].rson!=0)
            aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].rson].gcd);
    }

    int query(int l, int r, int val, int qa, int qb)
    {
        if (qa<=l && r<=qb)
        {
            return aint[val].gcd;
        }
        int mid,ans;
        mid=(l+r)/2;
        ans=0;
        if (qa<=mid)
        {
            if (aint[val].lson!=0)
                ans=__gcd(ans,query(l,mid,aint[val].lson,qa,qb));
        }
        if (qb>mid)
        {
            if (aint[val].rson!=0)
                ans=__gcd(ans,query(mid+1,r,aint[val].rson,qa,qb));
        }
        return ans;
    }

};

struct Node_baban
{
    signed lson;
    signed rson;
    AINT a;
};

Node_baban emptyNode_baban= {0,0,{0,{emptyNode}}};

class AINT_baban
{
public:
    signed sz;
    Node_baban aint[200000];

    void init()
    {
        sz=0;
        //aint.clear();
        aint[0]=emptyNode_baban;//aint.push_back(emptyNode_baban);
        aint[0].a.init();//aint.back().a.init();
    }

    void update(int l, int r, int val, int x, int y, int k)
    {
        if (l==r)
        {
            aint[val].a.update(0,lim,0,y,k,l,r);
            return;
        }
        int mid;
        mid=(l+r)/2;
        aint[val].a.update(0,lim,0,y,k,l,r);
        if (x<=mid)
        {
            if (aint[val].lson==0)
            {
                sz++;
                aint[val].lson=sz;
                aint[sz]=emptyNode_baban;//aint.push_back(emptyNode_baban);
                aint[sz].a.init();//aint.back().a.init();
            }
            update(l,mid,aint[val].lson,x,y,k);
        }
        else
        {
            if (aint[val].rson==0)
            {
                sz++;
                aint[val].rson=sz;
                aint[sz]=emptyNode_baban;//aint.push_back(emptyNode_baban);
                aint[sz].a.init();//aint.back().a.init();
            }
            update(mid+1,r,aint[val].rson,x,y,k);
        }
    }

    int query(int l, int r, int val, int x1, int x2, int y1, int y2)
    {
        if (x1<=l && r<=x2)
        {
            return aint[val].a.query(0,lim,0,y1,y2);
        }
        int mid,ans;
        mid=(l+r)/2;
        ans=0;
        if (x1<=mid)
        {
            if (aint[val].lson!=0)
                ans=__gcd(ans,query(l,mid,aint[val].lson,x1,x2,y1,y2));
        }
        if (x2>mid)
        {
            if (aint[val].rson!=0)
                ans=__gcd(ans,query(mid+1,r,aint[val].rson,x1,x2,y1,y2));
        }
        return ans;
    }
} hurkacz;

void init(signed R, signed C)
{
    hurkacz.init();
    cnt=0;
    /*
    int i;
    for (i=0;i<R;i++)
         nush[i].init();
    */
}

void update(signed P, signed Q, long long K)
{
    //nush[P].update(0,lim,0,Q,K);
    if (mp.find(Q)==mp.end())
    {
        mp[Q]=++cnt;
        ainta[mp[Q]].init();
    }
    ainta[mp[Q]].update(0,lim,0,P,K);
    hurkacz.update(0,lim,0,P,Q,K);
}

long long calculate(signed P, signed Q, signed U, signed V)
{
    /*
    int ans,i;
    ans=0;
    for (i=P;i<=U;i++)
    {
         ans=__gcd(ans,nush[i].query(0,lim,0,Q,V));
    }
    return ans;
    */
    return hurkacz.query(0,lim,0,P,U,Q,V);
}

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