Submission #620562

#	Time	Username	Problem	Language	Result	Execution time	Memory
620562		MadokaMagicaFan	Game (IOI13_game)	C++14	100 / 100	5776 ms	88268 KiB

game

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

using namespace std;

using ll = long long;
const ll inf = 1e9;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define fst                         first
#define scn                         second
/* #define ONPC */

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) { return a + rng()%(b-a+1); }

ll
gcd2(ll a, ll b)
{
    if (a == 0) return b;
    if (b == 0) return a;
    return gcd2(b, a%b);
}

struct treap{
    ll x, v;
    int s;
    int w;
    ll k;
    treap *l, *r;

    treap(ll _x, ll _k) {
        w = rand(0,10000);
        l = r = NULL;
        x = v = _x;
        k = _k;
        s = 1;
    }
};

using tp = treap*;

int size(tp x) { return (x == NULL ? 0 : x->s); }
ll xval(tp x) { return (x == NULL ? 0 : x->v); }

void
calc(tp x)
{
    if (x == NULL) return;
    x->s = 1 + size(x->l) + size(x->r);
    x->v = gcd2(x->x,gcd2(xval(x->l),xval(x->r)));
}

void 
split(tp t, tp& l, tp & r, ll k)
{
    if (t == NULL)
        l = r = NULL;
    else if (t->k > k)
        split(t->l, l, t->l, k), r = t;
    else
        split(t->r, t->r, r, k), l = t;
    calc(t);
}

void
unite(tp& t, tp l, tp r)
{
    if (l == NULL) t=r;
    else if (r == NULL) t=l;
    else if (l->w > r->w)
        unite(l->r,l->r,r), t = l;
    else
        unite(r->l,l,r->l), t = r;
    calc(t);
}


struct aint {
    int l, r;
    aint *la, *ra;
    tp v;

    aint(int _l, int _r)
        : l(_l), r(_r)
    {
        v = NULL;
        la = ra = NULL;
    }

    ll
    upd(int x, int y, ll val)
    {
        if (x < l || x > r) return getval(y,y);
        if (l == r)
            return set(y,val);

        if (!la) la = new aint(l, (l+r)>>1);
        if (!ra) ra = new aint(((l+r)>>1)+1, r);
        val = gcd2(la->upd(x,y,val), ra->upd(x,y,val));

        return set(y,val);
    }

    ll
    set(int y, ll val)
    {
        tp a, b, c;
        a = b = c = NULL;
        split(v, a, b, y-1);
        split(b, b, c, y);

        assert(size(b)<2);
        if (b == NULL)
            b = new treap(val, y);
        assert(b->k == y);
        b->x = val;
        calc(b);

        unite(v, a, b);
        unite(v, v, c);
        return val;
    }

    ll
    query(int lx, int rx, int ly, int ry)
    {
        if (rx < l || lx > r) return 0;
        if (lx <= l && r <= rx) return getval(ly,ry);

        ll ret = 0;
        if (la) ret = gcd2(ret, la->query(lx,rx,ly,ry));
        if (ra) ret = gcd2(ret, ra->query(lx,rx,ly,ry));
        return ret;
    }

    ll
    getval(int ly, int ry)
    {
        if (v == NULL) return 0;
        ll ret = 0;
        tp a, b, c;
        a = b = c = NULL;
        split(v, a, b, ly-1);
        split(b, b, c, ry);
        ret = xval(b);
        unite(v, a, b);
        unite(v, v, c);
        return ret;
    }
};

aint* root;

void
init(int R, int C)
{
    assert(R<=1e9);
    assert(C<=1e9);
    root = new aint(0,max(R,C)+100);
    return;
}

void
update(int p, int q, long long k)
{
    root->upd(p,q,k);
    return;
}

ll
calculate(int p, int q, int u, int v)
{
    /* if (p>u) swap(u,p); */
    /* if (q>v) swap(q,v); */
    return root->query(p, u, q, v);
}

#ifdef ONPC
void
solve()
{
    int r, c, q;
    cin >> r >> c >> q;
    init(r,c);

    int t, w, x, y;
    ll z;
    while(q--) {
        cin >> t;
        if (t == 1) {
            cin >> x >> y >> z;
            update(x,y,z);
        } else {
            cin >> w >> x >> y >> z;
            cout << calculate(w,x,y,z) << endl;
        }
    }
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

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