Submission #1156078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156078		alexdd	Game (IOI13_game)	C++20	100 / 100	12883 ms	36544 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int RESET_TIME = 200;

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 segtree
{
    vector<int> aint;
    vector<int> used_vals;
    int get_poz(int x)
    {
        assert(*lower_bound(used_vals.begin(),used_vals.end(),x) == x);
        return lower_bound(used_vals.begin(),used_vals.end(),x) - used_vals.begin();
    }
    void fake_upd(int poz)
    {
        used_vals.push_back(poz);
    }
    void init()
    {
        sort(used_vals.begin(),used_vals.end());
        used_vals.erase(unique(used_vals.begin(),used_vals.end()),used_vals.end());
        aint.clear();
        aint.resize(4*(int)used_vals.size() + 5, 0);
    }
    void clear()
    {
        aint.clear();
        used_vals.clear();
    }
    void internal_upd(int nod, int st, int dr, int poz, int newv, bool tip, segtree& c1, segtree& c2)
    {
        if(st==dr)
        {
            if(tip)
                aint[nod] = newv;
            else
                aint[nod] = __gcd(c1.qry(used_vals[st],used_vals[dr]), c2.qry(used_vals[st],used_vals[dr]));
            return;
        }
        int mij=(st+dr)/2;
        if(poz<=mij) internal_upd(nod*2,st,mij,poz,newv,tip,c1,c2);
        else internal_upd(nod*2+1,mij+1,dr,poz,newv,tip,c1,c2);
        aint[nod] = __gcd(aint[nod*2], aint[nod*2+1]);
    }
    void upd(int poz, int newv, bool tip, segtree& c1, segtree& c2)
    {
        internal_upd(1,0,(int)used_vals.size(),get_poz(poz),newv,tip,c1,c2);
    }
    int internal_qry(int nod, int st, int dr, int le, int ri)
    {
        if(le>ri)
            return 0;
        if(le==st && dr==ri)
            return aint[nod];
        int mij=(st+dr)/2;
        return __gcd(internal_qry(nod*2,st,mij,le,min(mij,ri)), internal_qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
    }
    int qry(int le, int ri)
    {
        le = lower_bound(used_vals.begin(),used_vals.end(),le) - used_vals.begin();
        ri = upper_bound(used_vals.begin(),used_vals.end(),ri)-used_vals.begin()-1;
        return internal_qry(1,0,(int)used_vals.size(),le,ri);
    }
};
segtree emp;
struct segtree_2D
{
    vector<int> used_vals;
    vector<segtree> aint;
    int get_poz(int x)
    {
        assert(*lower_bound(used_vals.begin(),used_vals.end(),x) == x);
        return lower_bound(used_vals.begin(),used_vals.end(),x) - used_vals.begin();
    }
    void fake_upd(int nod, int st, int dr, int pozx, int pozy)
    {
        if(st==dr)
        {
            aint[nod].fake_upd(pozy);
            return;
        }
        aint[nod].fake_upd(pozy);

        int mij=(st+dr)/2;
        if(pozx<=mij) fake_upd(nod*2,st,mij,pozx,pozy);
        else fake_upd(nod*2+1,mij+1,dr,pozx,pozy);
    }
    void init(vector<pair<int,int>> init_upds)
    {
        for(auto [x,y]:init_upds)
            used_vals.push_back(x);
        sort(used_vals.begin(),used_vals.end());
        used_vals.erase(unique(used_vals.begin(),used_vals.end()),used_vals.end());

        aint.clear();
        aint.resize(4*(int)used_vals.size() + 5);

        for(int i=0;i<aint.size();i++)
            aint[i].clear();
        for(auto [x,y]:init_upds)
        {
            fake_upd(1,0,(int)used_vals.size(),get_poz(x),y);//--------------------------------------
            //aint[get_poz(x)].fake_upd(y);
        }
        for(int i=0;i<aint.size();i++)
            aint[i].init();
    }
    void internal_upd(int nod, int st, int dr, int pozx, int pozy, int newv)
    {
        if(st==dr)
        {
            aint[nod].upd(pozy,newv,1,emp,emp);
            return;
        }

        int mij=(st+dr)/2;
        if(pozx<=mij) internal_upd(nod*2,st,mij,pozx,pozy,newv);
        else internal_upd(nod*2+1,mij+1,dr,pozx,pozy,newv);

        aint[nod].upd(pozy,newv,0,aint[nod*2],aint[nod*2+1]);

    }
    void upd(int pozx, int pozy, int newv)
    {
        internal_upd(1,0,(int)used_vals.size(),get_poz(pozx),pozy,newv);//----------------------------------------------------
        //aint[get_poz(pozx)].upd(pozy,newv,1);
    }
    int internal_qry(int nod, int st, int dr, int le, int ri, int yle, int yri)
    {
        if(le>ri)
            return 0;
        if(le==st && dr==ri)
            return aint[nod].qry(yle,yri);
        int mij=(st+dr)/2;
        return __gcd(internal_qry(nod*2,st,mij,le,min(mij,ri),yle,yri),
                     internal_qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,yle,yri));
    }
    int qry(int xle, int xri, int yle, int yri)
    {
        xle = lower_bound(used_vals.begin(),used_vals.end(),xle)-used_vals.begin();
        xri = upper_bound(used_vals.begin(),used_vals.end(),xri)-used_vals.begin()-1;

        /*int gc=0;
        for(int i=xle;i<=xri;i++)
            gc = __gcd(gc, aint[i].qry(yle,yri));
        return gc;*/

        return internal_qry(1,0,(int)used_vals.size(),xle,xri,yle,yri);
    }
};


void init(int32_t R, int32_t C)
{

}

vector<pair<int,int>> elems;
map<pair<int,int>,bool> isold;
map<pair<int,int>,int> new_elems,all_elems;

segtree_2D s2d;
void recalc()
{
    for(auto x:new_elems)
        elems.push_back(x.first);
    new_elems.clear();

    for(auto x:elems)
        isold[x]=1;

    s2d.init(elems);
    for(auto x:elems) s2d.upd(x.first,x.second,all_elems[x]);
}

void update(int32_t P, int32_t Q, long long K)
{
    all_elems[{P,Q}] = K;

    if(isold[{P,Q}])
    {
        s2d.upd(P,Q,K);
    }
    else
        new_elems[{P,Q}] = K;

    if((int)new_elems.size() >= RESET_TIME)
        recalc();
}

long long calculate(int32_t P, int32_t Q, int32_t U, int32_t V)
{
    int xle = min(P,U), xri = max(P,U), yle = min(Q,V), yri = max(Q,V);
    int gc = 0;
    if(!elems.empty()) gc = s2d.qry(xle,xri,yle,yri);
    for(auto cv:new_elems)
    {
        int x = cv.first.first, y = cv.first.second, val = cv.second;
        if(xle<=x && x<=xri && yle<=y && y<=yri)
            gc = __gcd(gc, val);
    }
    return gc;
}

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