Submission #1126199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126199		MisterReaper	Game (IOI13_game)	C++17	100 / 100	3305 ms	62780 KiB

game

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

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

// #define DEBUG
#ifdef DEBUG
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

std::mt19937_64 rng(23);

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

int R, C;

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

    node* root = nullptr;
    treap() {}
    treap(node* x) : root(x) {}

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

    void pull(node*& v) {
        if (!v) {
            return;
        }
        v->sum = gcd(sum(v->l), sum(v->r), v->val);
        v->lo = (v->l ? v->l->lo : v->pos);
        v->hi = (v->r ? v->r->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->l, l, r->l);
            v = r;
        } else {
            merge(l->r, l->r, 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->r, v->r, r, p);
            l = v;
        } else {
            split(v->l, l, v->l, p);
            r = v;
        }
        pull(l);
        pull(r);
    }

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

    void update(node* v, int p, i64 x) {
        if (v->pos == p) {
            v->val = x;
        } else if (v->pos < p) {
            update(v->r, p, x);
        } else {
            update(v->l, p, x);
        }
        pull(v);
    }

    void insert(int p, i64 x) {
        if (find(p)) {
            update(root, p, x);
        } else {
            node *l, *r;
            split(root, l, r, p);
            merge(root, l, new node(p, x));
            merge(root, root, r);
        }
        print();
        debug();
    }

    i64 query(node* v, int l, int r) {
        if (r < v->lo || v->hi < l) {
            return 0;
        } else if (l <= v->lo && v->hi <= r) {
            debug("querying treap: ", l, r, v->sum);
            return v->sum;
        }

        i64 ans = ((l <= v->pos && v->pos <= r) ? v->val : 0);
        if (v->l) ans = std::gcd(ans, query(v->l, l, r));
        if (v->r) ans = std::gcd(ans, query(v->r, l, r));
        return ans;
    }
    i64 query(int l, int r) {
        debug("query: ", l, r);
        if (!root) {
            return 0;
        }
        return query(root, l, r);
    }

    void print_vertex(node* v) {
        if (!v) {
            return;
        }
        print_vertex(v->l);
        debug(v->pos, v->val);
        print_vertex(v->r);
    }
    void print() {
        #ifdef DEBUG
            debug("treap: ");
            print_vertex(root);
        #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 y) {
        i64 x = 0;
        if (l) x = std::gcd(x, l->tree.query(y, y));
        if (r) x = std::gcd(x, r->tree.query(y, y));
        tree.insert(y, x);
    }
    void update(int x, int y, i64 k) {
        if (lo == hi) {
            tree.insert(y, k);
            return;
        }
        int mid = (lo + hi) >> 1;
        if (x <= mid) {
            if (!l) {
                l = new segtree(lo, mid);
            }
            l->update(x, y, k);
        } else {
            if (!r) {
                r = new segtree(mid + 1, hi);
            }
            r->update(x, y, k);
        }
        fix(y);
    }

    i64 query(int a, int b, int c, int d) {
        if (b < lo || hi < a) {
            return 0;
        } else if (a <= lo && hi <= b) {
            i64 res = tree.query(c, d);
            tree.print();
            debug("single:", lo, hi, res);
            return res;
        }
        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));
        debug(lo, hi, res);
        return res;
    }
} root;

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

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

i64 calculate(int P, int Q, int U, int V) {
    debug("query", P, Q, U, V);
    return root.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