제출 #1156018

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

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
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.resize(4*(int)used_vals.size() + 5);
    }
    void clear()
    {
        aint.clear();
        used_vals.clear();
    }
    void internal_upd(int nod, int st, int dr, int poz, int newv, bool tip)
    {
        if(st==dr)
        {
            if(tip)
                aint[nod] = newv;
            else
                aint[nod] = __gcd(aint[nod], newv);
            return;
        }
        int mij=(st+dr)/2;
        if(poz<=mij) internal_upd(nod*2,st,mij,poz,newv,tip);
        else internal_upd(nod*2+1,mij+1,dr,poz,newv,tip);
        aint[nod] = __gcd(aint[nod*2], aint[nod*2+1]);
    }
    void upd(int poz, int newv, bool tip)
    {
        internal_upd(1,0,(int)used_vals.size()-1,get_poz(poz),newv,tip);
    }
    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)
    {
        return internal_qry(1,0,(int)used_vals.size()-1,get_poz(le),get_poz(ri));
    }
};
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(auto [x,y]:init_upds)
            fake_upd(1,0,(int)used_vals.size()-1,get_poz(x),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);
            return;
        }
        aint[nod].upd(pozy,newv,0);

        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);

    }
    void upd(int pozx, int pozy, int newv)
    {
        internal_upd(1,0,(int)used_vals.size()-1,get_poz(pozx),pozy,newv);
    }
    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)
    {
        return internal_qry(1,0,(int)used_vals.size()-1,get_poz(xle),get_poz(xri),yle,yri);
    }
};

const int BUC = 100;
const int CNT_BUC = 100;
const int RESET_TIME = 100;

void init(int32_t R, int32_t C)
{

}

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

segtree_2D s2d;
void recalc()
{
    for(auto x:new_elems)
        elems.push_back(x);
    new_elems.clear();
    isold.clear();
    vector<pair<int,int>> elem_pozs;
    for(auto x:elems)
    {
        elem_pozs.push_back(x.first);
        isold[x.first]=1;
    }

    s2d.init(elem_pozs);
}

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

    /*if(update_cnt%RESET_TIME==0)
        recalc();
    update_cnt++;
    if(isold[{P,Q}])
    {
        s2d.upd(P,Q,K);
    }
    else
        new_elems.push_back({{P,Q},K});*/
}

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;
    //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: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20