oj.uz

답안 #1009429

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009429 2024-06-27T13:54:31 Z CYMario 게임 (IOI13_game) C++17
100 / 100
 1959 ms 20636 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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