Submission #1009429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009429		CYMario	Game (IOI13_game)	C++17	100 / 100	1959 ms	20636 KiB

game

#include <algorithm>
#include "game.h"
typedef long long i64;
i64 gcd(i64 a, i64 b)
{
    // a = std::abs(a), b = std::abs(b);
    if (!a || !b)
        return a | b;
    int az = __builtin_ctzll(a), bz = __builtin_ctzll(b), z = std::min(az, bz);
    b >>= bz;
    while (a)
    {
        a >>= az;
        i64 d = std::abs(a - b);
        az = __builtin_ctzll(d);
        if (a < b)
            b = a;
        a = d;
    }
    return b << z;
}
const int N = 22010, V = 1000000010, LOG_V = 30;

int lev(int x) { return x ? (32 - __builtin_clz(x)) : 1; }

std::pair<int, int> lca(int u, int v)
{
    if (u == v)
        return std::make_pair(u, v);
    int log_len = 32 - __builtin_clz(u ^ v);
    int len = 1 << log_len;
    int l = (u >> log_len) << log_len;
    return std::make_pair(l, l | (len - 1));
}

namespace seg_y
{
    int log_interval_y;

    struct node_y
    {
        int ch[2];
        int l, r;
        i64 sum;
    } tr[(N * LOG_V) << 2];

    int cnt;
    int new_node() { return ++cnt; }

    void init(int _lg_interval) { log_interval_y = _lg_interval, cnt = 0; }
    int new_root()
    {
        int ret = new_node();
        tr[ret].l = 0, tr[ret].r = (1 << log_interval_y) - 1;
        tr[ret].sum = 0;
        return ret;
    }

    void pushup(int u) { tr[u].sum = gcd(tr[tr[u].ch[0]].sum, tr[tr[u].ch[1]].sum); }

    bool handle(int u, int son, int pos, i64 val)
    {
        bool ret = true;
        // case 1 : child node is null
        if (!tr[u].ch[son])
        {
            int v = new_node();
            tr[u].ch[son] = v; // set u's child
            tr[v].sum = val;   // set val
            tr[v].l = tr[v].r = pos;
            pushup(u);
        }
        // case 2 : child node is a single point
        else if (tr[tr[u].ch[son]].l == tr[tr[u].ch[son]].r)
        {
            // case 2-1 : child node's position = pos
            if (tr[tr[u].ch[son]].l == pos)
                tr[tr[u].ch[son]].sum = val, pushup(u);
            // case 2-2 not same pos, merge it to their lca interval (virtual node)
            else
            {
                std::pair<int, int> _lca = lca(pos, tr[tr[u].ch[son]].l);

                int f = new_node();
                tr[f].l = _lca.first, tr[f].r = _lca.second;

                int v = new_node();
                tr[v].sum = val, tr[v].l = tr[v].r = pos;

                // u's child becomes lca
                tr[f].ch[0] = pos < tr[tr[u].ch[son]].l ? v : tr[u].ch[son];
                tr[f].ch[1] = (v ^ tr[u].ch[son]) ^ tr[f].ch[0];
                tr[u].ch[son] = f;

                pushup(f), pushup(u);
            }
        }
        // case 3 : child node is an interval and pos \not\in interval
        else if (pos < tr[tr[u].ch[son]].l || pos > tr[tr[u].ch[son]].r)
        {
            std::pair<int, int> _lca = lca(pos, tr[tr[u].ch[son]].l);
            // same as case 2-2, because lca(u, v) = lca(son_u, son_v)
            int f = new_node();
            tr[f].l = _lca.first, tr[f].r = _lca.second;

            int v = new_node();
            tr[v].sum = val, tr[v].l = tr[v].r = pos;

            // u's child becomes lca
            tr[f].ch[0] = pos < tr[tr[u].ch[son]].l ? v : tr[u].ch[son];
            tr[f].ch[1] = (v ^ tr[u].ch[son]) ^ tr[f].ch[0];
            tr[u].ch[son] = f;

            pushup(f), pushup(u);
        }
        // case 4 : child node is an interval and pos \in interval
        else
            ret = false; // continue recurrence
        return ret;
    }
    void _set(int u, int pos, i64 val)
    {
        int m = (tr[u].l + tr[u].r) >> 1;
        if (pos <= m)
        {
            bool ret = handle(u, 0, pos, val);
            if (!ret)
                _set(tr[u].ch[0], pos, val), pushup(u);
        }
        else
        {
            bool ret = handle(u, 1, pos, val);
            if (!ret)
                _set(tr[u].ch[1], pos, val), pushup(u);
        }
    }
    i64 _query(int u, int l, int r)
    {
        if (!u)
            return 0;
        int L = tr[u].l, R = tr[u].r;
        if (L > r || R < l)
            return 0;
        if (l <= L && R <= r)
            return tr[u].sum;
        return gcd(_query(tr[u].ch[0], l, r), _query(tr[u].ch[1], l, r));
    }
    int find_pos(int u, int pos)
    {
        while (u)
        {
            if (tr[u].r < pos || tr[u].l > pos)
                return 0;
            if (tr[u].l == tr[u].r)
                break;
            int m = (tr[u].l + tr[u].r) >> 1;
            u = tr[u].ch[pos > m];
        }
        return u;
    }
    int clone(int u)
    {
        int ret = new_node();
        tr[ret].l = tr[u].l, tr[ret].r = tr[u].r;
        tr[ret].sum = tr[u].sum;
        tr[ret].ch[0] = tr[u].ch[0] ? clone(tr[u].ch[0]) : 0;
        tr[ret].ch[1] = tr[u].ch[1] ? clone(tr[u].ch[1]) : 0;
        return ret;
    }
}

namespace seg_x
{
    int log_interval_x;
    struct node_x
    {
        int ch[2];
        int l, r;
        int rt;
    } tr[N << 1];
    int cnt, root;
    int new_node() { return ++cnt; }
    void init(int _lg_interval)
    {
        log_interval_x = _lg_interval, cnt = 0;
        root = new_node();
        tr[root].l = 0, tr[root].r = (1 << log_interval_x) - 1;
        tr[root].rt = seg_y::new_root();
    }

    void pushup(int u, int y)
    {
        int lcpos = seg_y::find_pos(tr[tr[u].ch[0]].rt, y);
        int rcpos = seg_y::find_pos(tr[tr[u].ch[1]].rt, y);
        i64 res = gcd(seg_y::tr[lcpos].sum, seg_y::tr[rcpos].sum);
        seg_y::_set(tr[u].rt, y, res);
    }

    bool handle(int u, int son, int x, int y, i64 val)
    {
        bool ret = true;
        if (!tr[u].ch[son])
        {
            int v = new_node();
            tr[u].ch[son] = v;
            tr[v].l = tr[v].r = x;
            tr[v].rt = seg_y::new_root();
            seg_y::_set(tr[v].rt, y, val);
            pushup(u, y);
        }
        else if (tr[tr[u].ch[son]].l == tr[tr[u].ch[son]].r)
        {
            if (tr[tr[u].ch[son]].l == x)
            {
                seg_y::_set(tr[tr[u].ch[son]].rt, y, val);
                pushup(u, y);
            }
            else
            {
                std::pair<int, int> _lca = lca(x, tr[tr[u].ch[son]].l);
                int f = new_node();
                tr[f].l = _lca.first, tr[f].r = _lca.second;
                tr[f].rt = seg_y::clone(tr[tr[u].ch[son]].rt);

                int v = new_node();
                tr[v].l = tr[v].r = x;
                tr[v].rt = seg_y::new_root();
                seg_y::_set(tr[v].rt, y, val);

                tr[f].ch[0] = x < tr[tr[u].ch[son]].l ? v : tr[u].ch[son];
                tr[f].ch[1] = (v ^ tr[u].ch[son]) ^ tr[f].ch[0];
                tr[u].ch[son] = f;

                pushup(f, y), pushup(u, y);
            }
        }
        else if (x < tr[tr[u].ch[son]].l || x > tr[tr[u].ch[son]].r)
        {
            std::pair<int, int> _lca = lca(x, tr[tr[u].ch[son]].l);
            int f = new_node();
            tr[f].l = _lca.first, tr[f].r = _lca.second;
            tr[f].rt = seg_y::clone(tr[tr[u].ch[son]].rt);

            int v = new_node();
            tr[v].l = tr[v].r = x;
            tr[v].rt = seg_y::new_root();
            seg_y::_set(tr[v].rt, y, val);

            tr[f].ch[0] = x < tr[tr[u].ch[son]].l ? v : tr[u].ch[son];
            tr[f].ch[1] = (v ^ tr[u].ch[son]) ^ tr[f].ch[0];
            tr[u].ch[son] = f;

            pushup(f, y), pushup(u, y);
        }
        else
            ret = false;
        return ret;
    }

    void _set(int u, int x, int y, i64 val)
    {
        int m = (tr[u].l + tr[u].r) >> 1;
        if (x <= m)
        {
            bool ret = handle(u, 0, x, y, val);
            if (!ret)
                _set(tr[u].ch[0], x, y, val), pushup(u, y);
        }
        else
        {
            bool ret = handle(u, 1, x, y, val);
            if (!ret)
                _set(tr[u].ch[1], x, y, val), pushup(u, y);
        }
    }

    void set(int x, int y, i64 val) { _set(root, x, y, val); }

    i64 _query(int u, int xl, int xr, int yl, int yr)
    {
        if (!u)
            return 0;
        int L = tr[u].l, R = tr[u].r;
        if (L > xr || R < xl)
            return 0;
        if (xl <= L && R <= xr)
            return seg_y::_query(tr[u].rt, yl, yr);
        return gcd(_query(tr[u].ch[0], xl, xr, yl, yr), _query(tr[u].ch[1], xl, xr, yl, yr));
    }

    i64 query(int xl, int xr, int yl, int yr) { return _query(root, xl, xr, yl, yr); }
}
// notice : initialize order : y first x second
void init(int R, int C) { seg_y::init(lev(C - 1)), seg_x::init(lev(R - 1)); }

void update(int P, int Q, i64 K) { seg_x::set(P, Q, K); }

i64 calculate(int P, int Q, int U, int V) { return seg_x::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