제출 #489291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489291		CYMario	Game (IOI13_game)	C++17	100 / 100	2845 ms	38440 KiB

game

// 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); }

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20