제출 #1167006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167006		12345678	게임 (IOI13_game)	C++17	10 / 100	13056 ms	5144 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

mt19937 rng(1);

ll r, c;

struct treap
{
    struct node
    {
        ll sz, key, vl, g;
        pair<ll, ll> idx;
        node *l, *r;
        node(ll vl, pair<ll, ll> idx): sz(1), key(rng()), vl(vl), g(vl), idx(idx), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt=0;
    ll size(pnode x)
    {
        return x?x->sz:0;
    }
    ll g(pnode x)
    {
        return x?x->g:0;
    }
    void update(pnode x)
    {
        if (!x) return;
        x->sz=size(x->l)+size(x->r)+1;
        x->g=gcd(gcd(g(x->l), g(x->r)), x->vl);
    }
    void merge(pnode l, pnode r, pnode &k)
    {
        if (!l) return k=r, void();
        if (!r) return k=l, void();
        if (l->key>=r->key) merge(l->r, r, l->r), k=l;
        else merge(l, r->l, r->l), k=r;
        update(k);
    }
    void split(pnode &l, pnode &r, pnode k, pair<ll, ll> idx)
    {
        if (!k) return l=r=0, void();
        if (k->idx>=idx) split(l, k->l, k->l, idx), r=k;
        else split(k->r, r, k->r, idx), l=k;
        update(l);
        update(r);
    }
    void split2(pnode &l, pnode &r, pnode k, ll key)
    {
        if (!k) return l=r=0, void();
        if (size(k->l)+1<=key) split2(k->r, r, k->r, key-(1+size(k->l))), l=k;
        else split2(l, k->l, k->l, key), r=k;
        update(l);
        update(r);
    }
    void add(pair<ll, ll> idx, ll vl)
    {
        pnode p1, p2, p3;
        split(p1, p2, rt, idx);
        if (!p2) return merge(p1, new node(vl, idx), rt), void();
        split2(p2, p3, p2, 1);
        if (p2->idx==idx) return p2->vl=vl, merge(p2, p3, p2), merge(p1, p2, rt), void();
        merge(p2, p3, p2);
        merge(new node(vl, idx), p2, p2);
        merge(p1, p2, rt);
    }
    ll query(ll l, ll r)
    {
        pnode p1, p2, p3;
        split(p1, p2, rt, {l, 0});
        split(p2, p3, p2, {r+1, 0});
        ll res=p2?p2->g:0;
        merge(p2, p3, p2);
        merge(p1, p2, rt);
        return res;
    }
    void traverse(pnode x)
    {
        if (!x) return;
        traverse(x->l);
        cout<<x->idx.first<<' '<<x->key<<' '<<x->g<<'\n';
        traverse(x->r);
    }
    treap(): rt(0){}
};
typedef treap* ptreap;
vector<ptreap> v;

void init(int R, int C) {
    r=R, c=C;
    for (int i=0; i<R; i++) v.push_back(new treap());
}

void update(int P, int Q, long long K) {
    //cout<<"P "<<P<<' '<<Q<<' '<<K<<'\n';
    v[P]->add({Q, P}, K);
    //cout<<"after update "<<v[P]->rt->g<<'\n';
}

long long calculate(int P, int Q, int U, int V) {
    ll res=0;
    //cout<<"q "<<P<<' '<<Q<<' '<<U<<' '<<V<<'\n';
    //v[0]->traverse(v[0]->rt);
    //cout<<"query row "<<i<<":"<<v[i]->query(Q, V)<<'\n', 
    for (int i=P; i<=U; i++) res=gcd(res, v[i]->query(Q, V));
    return res;
}

// g++ grader.cpp game3.cpp -o a

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