Submission #1009429

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1009429	2024-06-27T13:54:31 Z	CYMario	Game (IOI13_game)	C++17	100 / 100	1959 ms	20636 KB

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	504 KB	Output is correct

Subtask #2
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	303 ms	6680 KB	Output is correct
5	Correct	190 ms	6864 KB	Output is correct
6	Correct	327 ms	3800 KB	Output is correct
7	Correct	356 ms	3352 KB	Output is correct
8	Correct	221 ms	4180 KB	Output is correct
9	Correct	298 ms	3524 KB	Output is correct
10	Correct	316 ms	3152 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct

Subtask #3
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	420 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	531 ms	8868 KB	Output is correct
13	Correct	1035 ms	3564 KB	Output is correct
14	Correct	145 ms	748 KB	Output is correct
15	Correct	1054 ms	5352 KB	Output is correct
16	Correct	193 ms	7504 KB	Output is correct
17	Correct	474 ms	4124 KB	Output is correct
18	Correct	793 ms	7824 KB	Output is correct
19	Correct	680 ms	8024 KB	Output is correct
20	Correct	697 ms	7312 KB	Output is correct
21	Correct	1 ms	344 KB	Output is correct

Subtask #4
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	285 ms	6596 KB	Output is correct
13	Correct	205 ms	6924 KB	Output is correct
14	Correct	331 ms	3664 KB	Output is correct
15	Correct	356 ms	3548 KB	Output is correct
16	Correct	252 ms	4252 KB	Output is correct
17	Correct	318 ms	3404 KB	Output is correct
18	Correct	313 ms	3156 KB	Output is correct
19	Correct	520 ms	8748 KB	Output is correct
20	Correct	955 ms	3412 KB	Output is correct
21	Correct	144 ms	976 KB	Output is correct
22	Correct	1029 ms	5584 KB	Output is correct
23	Correct	196 ms	7508 KB	Output is correct
24	Correct	505 ms	4176 KB	Output is correct
25	Correct	783 ms	7888 KB	Output is correct
26	Correct	683 ms	8064 KB	Output is correct
27	Correct	697 ms	7504 KB	Output is correct
28	Correct	225 ms	9736 KB	Output is correct
29	Correct	659 ms	12884 KB	Output is correct
30	Correct	1415 ms	7572 KB	Output is correct
31	Correct	1248 ms	5460 KB	Output is correct
32	Correct	148 ms	848 KB	Output is correct
33	Correct	268 ms	844 KB	Output is correct
34	Correct	333 ms	9808 KB	Output is correct
35	Correct	530 ms	6092 KB	Output is correct
36	Correct	884 ms	10140 KB	Output is correct
37	Correct	713 ms	10408 KB	Output is correct
38	Correct	721 ms	9812 KB	Output is correct
39	Correct	616 ms	8276 KB	Output is correct
40	Correct	0 ms	344 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	286 ms	6588 KB	Output is correct
13	Correct	178 ms	6864 KB	Output is correct
14	Correct	294 ms	3816 KB	Output is correct
15	Correct	332 ms	3408 KB	Output is correct
16	Correct	208 ms	4316 KB	Output is correct
17	Correct	315 ms	3628 KB	Output is correct
18	Correct	299 ms	3232 KB	Output is correct
19	Correct	513 ms	8920 KB	Output is correct
20	Correct	912 ms	3412 KB	Output is correct
21	Correct	140 ms	852 KB	Output is correct
22	Correct	971 ms	5380 KB	Output is correct
23	Correct	179 ms	7508 KB	Output is correct
24	Correct	427 ms	3920 KB	Output is correct
25	Correct	720 ms	8084 KB	Output is correct
26	Correct	632 ms	7960 KB	Output is correct
27	Correct	617 ms	7448 KB	Output is correct
28	Correct	215 ms	9816 KB	Output is correct
29	Correct	635 ms	12884 KB	Output is correct
30	Correct	1289 ms	7492 KB	Output is correct
31	Correct	1172 ms	5456 KB	Output is correct
32	Correct	146 ms	888 KB	Output is correct
33	Correct	209 ms	848 KB	Output is correct
34	Correct	333 ms	9812 KB	Output is correct
35	Correct	497 ms	6224 KB	Output is correct
36	Correct	824 ms	10072 KB	Output is correct
37	Correct	721 ms	10324 KB	Output is correct
38	Correct	697 ms	9808 KB	Output is correct
39	Correct	250 ms	18256 KB	Output is correct
40	Correct	907 ms	20636 KB	Output is correct
41	Correct	1959 ms	15864 KB	Output is correct
42	Correct	1818 ms	11656 KB	Output is correct
43	Correct	449 ms	18512 KB	Output is correct
44	Correct	199 ms	852 KB	Output is correct
45	Correct	611 ms	8276 KB	Output is correct
46	Correct	1031 ms	19032 KB	Output is correct
47	Correct	983 ms	18740 KB	Output is correct
48	Correct	980 ms	18516 KB	Output is correct
49	Correct	0 ms	348 KB	Output is correct

Submission #1009429

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.0 / 17.0

Subtask #5 20.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
17.0 / 17.0

Subtask #5
20.0 / 20.0