Submission #863377

#	Time	Username	Problem	Language	Result	Execution time	Memory
863377		deepaung	Game (IOI13_game)	C++14	100 / 100	5509 ms	78264 KiB

game

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

#define f first
#define s second
#define pll pair<ll, ll>
#define ll long long

using namespace std;

mt19937 rnd(time(NULL));

ll R, C;

ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Treap {
    struct node {
        ll val, gcd, sz, pri;
        pll pos;
        node *l, *r;

        node(ll val=0, pll pos={0, 0}, node *l=NULL, node *r=NULL) : 
            val(val), gcd(val), sz(1), pri(rnd()), pos(pos), l(l), r(r) {}
    };

    node *root;

    Treap() : root(NULL) {}

    void recalc(node *cur) {
        if (cur == NULL) return;

        cur->sz = 1;
        cur->gcd = cur->val;
        if (cur->l != NULL)
            cur->sz += cur->l->sz, cur->gcd = gcd2(cur->gcd, cur->l->gcd);
        if (cur->r != NULL)
            cur->sz += cur->r->sz, cur->gcd = gcd2(cur->gcd, cur->r->gcd);
    }

    void split(node *cur, node *&left, node *&right, pll pos) {
        if (cur == NULL) {
            left = right = NULL;
            return;
        }

        if (cur->pos <= pos) {
            split(cur->r, cur->r, right, pos);
            left = cur;
        } else {
            split(cur->l, left, cur->l, pos);
            right = cur;
        }

        recalc(cur);
    }

    void merge(node *&cur, node *left, node *right) {
        if (left == NULL || right == NULL) {
            cur = (left != NULL ? left : right);
            return;
        }

        if (left->pri > right->pri) {
            merge(left->r, left->r, right);
            cur = left;
        } else {
            merge(right->l, left, right->l);
            cur = right;
        }

        recalc(cur);
    }

    void update(ll x, ll y, ll val) {
        node *left, *mid, *right;
        split(root, left, mid, {y, x-1});
        split(mid, mid, right, {y, x});

        merge(root, left, new node(val, {y, x}));
        merge(root, root, right);
    }

    ll gcd_range(ll yl, ll yr) {
        node *left, *mid, *right;
        split(root, left, mid, {yl, -1});
        split(mid, mid, right, {yr+1, -1});

        ll ans = (mid != NULL ? mid->gcd : 0);

        merge(root, left, mid);
        merge(root, root, right);

        return ans;
    }

};

struct Segtree {
    struct node {
        Treap treap;
        node *l, *r;

        node() : 
            treap(Treap()), l(NULL), r(NULL) {}
    };

    node *root;

    void update(ll x, ll y, ll val, node *&cur, ll l, ll r) {
        if (cur == NULL) cur = new node();

        cur->treap.update(x, y, val);
        if (l == r) return;

        ll mid = (l + r) >> 1;
        if (x <= mid) update(x, y, val, cur->l, l, mid);
        else update(x, y, val, cur->r, mid+1, r);
    }

    ll gcd_range(ll xl, ll yl, ll xr, ll yr, node *cur, ll l, ll r) {
        if (cur == NULL) return 0;
        if (xr < l || r < xl) return 0;

        if (xl <= l && r <= xr) {
            return cur->treap.gcd_range(yl, yr);
        }

        ll mid = (l + r) >> 1;
        ll resl = gcd_range(xl, yl, xr, yr, cur->l, l, mid);
        ll resr = gcd_range(xl, yl, xr, yr, cur->r, mid+1, r);

        return gcd2(resl, resr);

        // if (xl == l && r == xr) {
        //     return cur->treap.gcd_range(yl, yr);
        // }

        // ll mid = (l + r) >> 1;
        // if (xr <= mid) {
        //     return gcd_range(xl, yl, xr, yr, cur->l, l, mid);
        // } else if (xl >= mid + 1) {
        //     return gcd_range(xl, yl, xr, yr, cur->r, mid+1, r);
        // } else {
        //     return gcd2(
        //         gcd_range(xl, yl, mid, yr, cur->l, l, mid),
        //         gcd_range(mid+1, yl, xr, yr, cur->r, mid+1, r)
        //     );
        // }
    }

} segtree;

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

void update(int x, int y, ll val) {
    x++, y++;
    segtree.update(x, y, val, segtree.root, 1, R);
}

ll calculate(int xl, int yl, int xr, int yr) {
    xl++, yl++, xr++, yr++;
    return segtree.gcd_range(xl, yl, xr, yr, segtree.root, 1, R);
}

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