Submission #1126355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126355		MisterReaper	Game (IOI13_game)	C++17	100 / 100	3271 ms	62812 KiB

game

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

using i64 = long long;
using u64 = unsigned long long;

#undef DEBUG
#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

i64 gcd(i64 a, i64 b, i64 c) {
    return std::gcd(std::gcd(a, b), c);
}

std::mt19937_64 rng(23);

struct treap {
    struct node {
        u64 wei = rng();
        int lo, hi;
        int pos;
        i64 val;
        i64 sum;
        node *lv = nullptr, *rv = nullptr;
        node() {}
        node(int p, i64 x) : lo(p), hi(p), pos(p), val(x), sum(x) {}
    };
    
    node *root = nullptr;
    treap() {}
    treap(node* v) : root(v) {}

    i64 sum(node* v) { return v ? v->sum : 0; }

    void pull(node*& v) {
        if (!v) {
            return;
        }
        v->sum = gcd(sum(v->lv), sum(v->rv), v->val);
        v->lo = (v->lv ? v->lv->lo : v->pos);
        v->hi = (v->rv ? v->rv->hi : v->pos);
    }

    void merge(node*& v, node* l, node* r) {
        if (!l || !r) {
            v = (l ? l : r);
            return;
        }
        if (l->wei < r->wei) {
            merge(r->lv, l, r->lv);
            v = r;
        } else {
            merge(l->rv, l->rv, r);
            v = l;
        }
        pull(v);
    }

    void split(node* v, node*& l, node*& r, int p) {
        if (!v) {
            l = nullptr;
            r = nullptr;
            return;
        }
        if (v->pos < p) {
            split(v->rv, v->rv, r, p);
            l = v;
        } else {
            split(v->lv, l, v->lv, p);
            r = v;
        }
        pull(l);
        pull(r);
    }

    bool find(int p) {
        node* v = root;
        while (v) {
            if (v->pos == p) {
                return true;
            } else if (v->pos < p) {
                v = v->rv;
            } else {
                v = v->lv;
            }
        }
        return false;
    }

    void update(node* v, int p, i64 x) {
        if (v->pos == p) {
            v->val = x;
        } else if (v->pos < p) {
            update(v->rv, p, x);
        } else {
            update(v->lv, p, x);
        }
        pull(v);
    }
    void update(int p, i64 x) {
        update(root, p, x);
    }
    void insert(int p, i64 x) {
        // debug("try to insert", p, x);
        if (find(p)) {
            // debug("found", p, x);
            update(p, x);
            // debug("success");
        } else {
            node *lv, *rv;
            // debug("try to split");
            split(root, lv, rv, p);
            // debug("try to merge #1");
            merge(lv, lv, new node(p, x));
            // debug("try to merge #2");
            merge(root, lv, rv);
            // debug("success");
        }
        debug_treap();
    }

    i64 query(node* v, int l, int r) {
        debug("query on treap: ", v->lo, v->hi, l, r);
        if (v->hi < l || r < v->lo) {
            return 0;
        } else if (l <= v->lo && v->hi <= r) {
            return v->sum;
        }
        i64 res = ((l <= v->pos && v->pos <= r) ? v->val : 0);
        if (v->lv) res = std::gcd(res, query(v->lv, l, r));
        if (v->rv) res = std::gcd(res, query(v->rv, l, r));
        return res;
    }
    i64 query(int l, int r) {
        if (!root) {
            return 0;
        }
        debug_treap();
        return query(root, l, r);
    }

    void debug_vertex(node* v) {
        if (v->lv) debug_vertex(v->lv);
        debug(v->pos, v->val, v->sum);
        if (v->rv) debug_vertex(v->rv);
    }
    void debug_treap() {
        #ifdef DEBUG
            debug("treap: ");
            if (root) debug_vertex(root);
            debug();
        #endif
    }
};

struct segtree {
    int lo, hi;
    segtree *l = nullptr, *r = nullptr;
    treap tree;

    segtree() {}
    segtree(int a, int b) : lo(a), hi(b) {}

    void fix(int q) {
        debug("try to fix", q);
        i64 res = 0;
        debug("try left node");
        if (l) res = std::gcd(res, l->tree.query(q, q));
        debug("try right node");
        if (r) res = std::gcd(res, r->tree.query(q, q));
        debug("add", q, res);
        tree.insert(q, res);
        debug("success");
    }
    void update(int p, int q, i64 k) {
        if (lo == hi) {
            debug("single treap insert: ", q, k);
            tree.insert(q, k);
            return;
        }
        int mid = (lo + hi) >> 1;
        if (p <= mid) {
            if (!l) {
                l = new segtree(lo, mid);
            }
            l->update(p, q, k);
        } else {
            if (!r) {
                r = new segtree(mid + 1, hi);
            }
            r->update(p, q, k);
        }
        fix(q);
    }

    i64 query(int a, int b, int c, int d) {
        if (hi < a || b < lo) {
            return 0;
        } else if (a <= lo && hi <= b) {
            return tree.query(c, d);
        }
        int mid = (a + b) >> 1;
        i64 res = 0;
        if (l) res = std::gcd(res, l->query(a, b, c, d));
        if (r) res = std::gcd(res, r->query(a, b, c, d));
        return res;
    }
} tree;

void init(int R, int C) {
    tree = segtree(0, R - 1);
}

void update(int P, int Q, i64 K) {
    debug("update: ", P, Q, K);
    tree.update(P, Q, K);
}

i64 calculate(int P, int Q, int U, int V) {
    debug("query: ", P, Q, U, V);
    return tree.query(P, U, Q, V);
}

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