제출 #1167014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167014		12345678	Game (IOI13_game)	C++17	100 / 100	10205 ms	79064 KiB

game

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

using namespace std;

#define ll long long

mt19937 rng(time(0));

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=p2->g=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, -1});
        split(p2, p3, p2, {r+1, -1});
        ll res=g(p2);
        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;

struct segtree
{
    struct node
    {
        ptreap t;
        node *nl, *nr;
        node(): t(new treap()), nl(0), nr(0){}
    };
    typedef node* pnode;
    pnode rt;
    void update(ll l, ll r, pnode &k, ll idx, ll y, ll vl)
    {
        if (!k) k=new node();
        k->t->add({y, idx}, vl);
        if (l==r) return;
        ll md=(l+r)/2;
        if (idx<=md) update(l, md, k->nl, idx, y, vl);
        else update(md+1, r, k->nr, idx, y, vl);
    }
    ll query(ll l, ll r, pnode k, ll ql, ll qr, ll x, ll y)
    {
        if (!k||qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return k->t->query(x, y);
        int md=(l+r)/2;
        return gcd(query(l, md, k->nl, ql, qr, x, y), query(md+1, r, k->nr, ql, qr, x, y));
    }
} s;

void init(int R, int C) {
    r=R, c=C;
}

void update(int P, int Q, long long K) {
    s.update(0, r-1, s.rt, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return s.query(0, r-1, s.rt, P, U, Q, V);
}

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

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