oj.uz

Submission #489291

# Submission time Handle Problem Language Result Execution time Memory
489291 2021-11-22T03:40:06 Z CYMario Game (IOI13_game) C++17
100 / 100
 2845 ms 38440 KB 
// interaction header
#include "game.h"
typedef long long ll;
struct ii
{
    int first, second;
    ii(int _a = 0, int _b = 0) : first(_a), second(_b) {}
};

inline ll gcd(ll x, ll y)
{
    if (!x)
        return y;
    if (!y)
        return x;
    if (x < 0)
        x = -x;
    if (y < 0)
        y = -y;
    ll t = __builtin_ctzll(x | y);
    x >>= __builtin_ctzll(x);
    do
    {
        y >>= __builtin_ctzll(y);
        if (x > y)
        {
            ll tmp = x;
            x = y;
            y = tmp;
        }
        y -= x;
    } while (y);
    return x << t;
}

inline ll func(ll X, ll Y) { return gcd(X, Y); }

// 2D Dynamic Query Tree from errorgorn

// find lca of 2 nodes
ii lca(int l, int r, int pos)
{
    if (pos < l)
    {
        int p = 32 - __builtin_clz(pos ^ l);
        int lp = (pos >> p) << p;
        return ii(lp, lp + (1 << p) - 1);
    }
    if (r < pos)
    {
        int p = 32 - __builtin_clz(r ^ pos);
        int lp = (l >> p) << p;
        return ii(lp, lp + (1 << p) - 1);
    }
    return ii(pos, 0);
}

struct node
{
    int s, e, m;
    ll val = 0;
    node *l = nullptr, *r = nullptr;

    node(int _s, int _e)
    {
        s = _s, e = _e, m = (s + e) >> 1;
    }

    bool inside(int i)
    {
        return s <= i && i <= e;
    }

    void update(int i, ll j)
    {
        if (s == e)
            val = j;
        else
        {
            if (i <= m)
            {
                if (l == nullptr)
                    l = new node(i, i);
                else if (!l->inside(i))
                {
                    node *temp = l;
                    ii child = lca(l->s, l->e, i);
                    l = new node(child.first, child.second);
                    if (temp->e <= l->m)
                        l->l = temp;
                    else
                        l->r = temp;
                }
                l->update(i, j);
            }
            else
            {
                if (r == nullptr)
                    r = new node(i, i);
                else if (!r->inside(i))
                {
                    node *temp = r;
                    ii child = lca(r->s, r->e, i);
                    r = new node(child.first, child.second);
                    if (temp->e <= r->m)
                        r->l = temp;
                    else
                        r->r = temp;
                }
                r->update(i, j);
            }
            val = func((l == nullptr) ? 0 : l->val, (r == nullptr) ? 0 : r->val);
        }
    }

    ll query(int i, int j)
    {
        if (i <= s && e <= j)
            return val;
        else if (j <= m)
            return (l == nullptr) ? 0 : l->query(i, j);
        else if (m < i)
            return (r == nullptr) ? 0 : r->query(i, j);
        else
            return func((l == nullptr) ? 0 : l->query(i, m), (r == nullptr) ? 0 : r->query(m + 1, j));
    }

    node *clone()
    {
        node *res = new node(s, e);
        res->val = val;
        res->l = (l == nullptr) ? nullptr : l->clone();
        res->r = (r == nullptr) ? nullptr : r->clone();
        return res;
    }
};

struct node2d
{
    int s, e, m;
    node *val = new node(0, (1 << 30) - 1);
    node2d *l = nullptr, *r = nullptr;

    node2d(int _s, int _e)
    {
        s = _s, e = _e, m = s + e >> 1;
    }

    bool inside(int i)
    {
        return s <= i && i <= e;
    }

    void update(int i, int j, ll k)
    {
        if (s == e)
            val->update(j, k);
        else
        {
            if (i <= m)
            {
                if (l == nullptr)
                    l = new node2d(i, i);
                else if (!l->inside(i))
                {
                    node2d *temp = l;
                    ii child = lca(l->s, l->e, i);
                    l = new node2d(child.first, child.second);
                    if (temp->e <= l->m)
                        l->l = temp;
                    else
                        l->r = temp;
                    l->val = temp->val->clone();
                }
                l->update(i, j, k);
            }
            else
            {
                if (r == nullptr)
                    r = new node2d(i, i);
                else if (!r->inside(i))
                {
                    node2d *temp = r;
                    ii child = lca(r->s, r->e, i);
                    r = new node2d(child.first, child.second);
                    if (temp->e <= r->m)
                        r->l = temp;
                    else
                        r->r = temp;
                    r->val = temp->val->clone();
                }
                r->update(i, j, k);
            }
            val->update(j, func((l == nullptr) ? 0 : l->val->query(j, j), (r == nullptr) ? 0 : r->val->query(j, j)));
        }
    }

    ll query(int i, int j, int i2, int j2)
    {
        if (i <= s && e <= j)
            return val->query(i2, j2);
        else if (j <= m)
            return (l == nullptr) ? 0 : l->query(i, j, i2, j2);
        else if (m < i)
            return (r == nullptr) ? 0 : r->query(i, j, i2, j2);
        else
            return func((l == nullptr) ? 0 : l->query(i, m, i2, j2), (r == nullptr) ? 0 : r->query(m + 1, j, i2, j2));
    }
} *root = new node2d(0, (1 << 30) - 1);

void init(int R, int C) {}

void update(int P, int Q, ll K) { root->update(P, Q, K); }

ll calculate(int P, int Q, int U, int V) { return root->query(P, U, Q, V); }

Compilation message

game.cpp: In constructor 'node2d::node2d(int, int)':
game.cpp:146:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |         s = _s, e = _e, m = s + e >> 1;
      |                             ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 280 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 276 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 280 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 370 ms 10212 KB Output is correct
5 Correct 253 ms 10476 KB Output is correct
6 Correct 367 ms 7064 KB Output is correct
7 Correct 434 ms 6828 KB Output is correct
8 Correct 272 ms 5084 KB Output is correct
9 Correct 427 ms 6928 KB Output is correct
10 Correct 421 ms 6608 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 715 ms 12460 KB Output is correct
13 Correct 1289 ms 5820 KB Output is correct
14 Correct 203 ms 1580 KB Output is correct
15 Correct 1393 ms 7236 KB Output is correct
16 Correct 311 ms 11072 KB Output is correct
17 Correct 617 ms 7392 KB Output is correct
18 Correct 1191 ms 11476 KB Output is correct
19 Correct 969 ms 11536 KB Output is correct
20 Correct 955 ms 11008 KB Output is correct
21 Correct 0 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 268 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 276 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 347 ms 10136 KB Output is correct
13 Correct 272 ms 10440 KB Output is correct
14 Correct 391 ms 7140 KB Output is correct
15 Correct 438 ms 6852 KB Output is correct
16 Correct 289 ms 5128 KB Output is correct
17 Correct 423 ms 6896 KB Output is correct
18 Correct 395 ms 6612 KB Output is correct
19 Correct 747 ms 12484 KB Output is correct
20 Correct 1313 ms 5784 KB Output is correct
21 Correct 193 ms 1620 KB Output is correct
22 Correct 1406 ms 6984 KB Output is correct
23 Correct 272 ms 11076 KB Output is correct
24 Correct 580 ms 7252 KB Output is correct
25 Correct 1253 ms 11536 KB Output is correct
26 Correct 985 ms 11612 KB Output is correct
27 Correct 919 ms 11000 KB Output is correct
28 Correct 352 ms 16708 KB Output is correct
29 Correct 982 ms 19360 KB Output is correct
30 Correct 1837 ms 13028 KB Output is correct
31 Correct 1723 ms 10312 KB Output is correct
32 Correct 212 ms 1680 KB Output is correct
33 Correct 288 ms 1732 KB Output is correct
34 Correct 431 ms 16500 KB Output is correct
35 Correct 671 ms 9076 KB Output is correct
36 Correct 1519 ms 16812 KB Output is correct
37 Correct 1107 ms 16904 KB Output is correct
38 Correct 1093 ms 16436 KB Output is correct
39 Correct 901 ms 13168 KB Output is correct
40 Correct 0 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 280 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 390 ms 10156 KB Output is correct
13 Correct 253 ms 10428 KB Output is correct
14 Correct 443 ms 7160 KB Output is correct
15 Correct 506 ms 6956 KB Output is correct
16 Correct 283 ms 4988 KB Output is correct
17 Correct 463 ms 6984 KB Output is correct
18 Correct 394 ms 6524 KB Output is correct
19 Correct 732 ms 12440 KB Output is correct
20 Correct 1265 ms 6000 KB Output is correct
21 Correct 193 ms 1476 KB Output is correct
22 Correct 1434 ms 7004 KB Output is correct
23 Correct 284 ms 11128 KB Output is correct
24 Correct 607 ms 7428 KB Output is correct
25 Correct 1239 ms 11504 KB Output is correct
26 Correct 964 ms 11576 KB Output is correct
27 Correct 877 ms 10896 KB Output is correct
28 Correct 372 ms 16608 KB Output is correct
29 Correct 943 ms 19368 KB Output is correct
30 Correct 1825 ms 13020 KB Output is correct
31 Correct 1681 ms 10176 KB Output is correct
32 Correct 202 ms 1484 KB Output is correct
33 Correct 303 ms 1776 KB Output is correct
34 Correct 419 ms 16452 KB Output is correct
35 Correct 672 ms 9172 KB Output is correct
36 Correct 1535 ms 16864 KB Output is correct
37 Correct 1111 ms 17040 KB Output is correct
38 Correct 1117 ms 16280 KB Output is correct
39 Correct 553 ms 37316 KB Output is correct
40 Correct 1796 ms 38440 KB Output is correct
41 Correct 2845 ms 28416 KB Output is correct
42 Correct 2648 ms 21108 KB Output is correct
43 Correct 628 ms 36420 KB Output is correct
44 Correct 246 ms 1476 KB Output is correct
45 Correct 878 ms 12928 KB Output is correct
46 Correct 2044 ms 36792 KB Output is correct
47 Correct 2023 ms 36848 KB Output is correct
48 Correct 1924 ms 36240 KB Output is correct
49 Correct 0 ms 204 KB Output is correct