Submission #722496

#	Time	Username	Problem	Language	Result	Execution time	Memory
722496		finn__	게임 (IOI13_game)	C++17	63 / 100	1854 ms	256000 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

int const R = 1 << 30, C = 1 << 30;
//                     ^ really good programming language

struct NodeY
{
    unique_ptr<NodeY> l, r;
    long long g;

    void update(int Q, long long K, int A, int B)
    {
        if (A == B)
        {
            g = K;
            return;
        }
        if (Q <= (A + B) / 2)
            (l ? l : l = make_unique<NodeY>())->update(Q, K, A, (A + B) / 2);
        else
            (r ? r : r = make_unique<NodeY>())->update(Q, K, (A + B) / 2 + 1, B);
        g = gcd(l ? l->g : 0, r ? r->g : 0);
    }

    long long calculate(int Q, int V, int A, int B)
    {
        if (B < Q || A > V)
            return 0;
        if (Q <= A && B <= V)
            return g;
        return gcd(l ? l->calculate(Q, V, A, (A + B) / 2) : 0,
                   r ? r->calculate(Q, V, (A + B) / 2 + 1, B) : 0);
    }
};

struct NodeX
{
    unique_ptr<NodeX> l, r;
    unique_ptr<NodeY> y;

    void update(int P, int Q, long long K, int A, int B)
    {
        if (!y)
            y = make_unique<NodeY>();
        if (A == B)
        {
            y->update(Q, K, 0, C - 1);
            return;
        }

        if (P <= (A + B) / 2)
            (l ? l : l = make_unique<NodeX>())->update(P, Q, K, A, (A + B) / 2);
        else
            (r ? r : r = make_unique<NodeX>())->update(P, Q, K, (A + B) / 2 + 1, B);

        y->update(Q,
                  gcd(l && l->y ? l->y->calculate(Q, Q, 0, C - 1) : 0,
                      r && r->y ? r->y->calculate(Q, Q, 0, C - 1) : 0),
                  0, C - 1);
    }

    long long calculate(int P, int Q, int U, int V, int A, int B)
    {
        if (B < P || A > U)
            return 0;
        if (P <= A && B <= U)
            return y ? y->calculate(Q, V, 0, C - 1) : 0;
        return gcd(l ? l->calculate(P, Q, U, V, A, (A + B) / 2) : 0,
                   r ? r->calculate(P, Q, U, V, (A + B) / 2 + 1, B) : 0);
    }
};

NodeX root;

void init(int R, int C) {}

void update(int P, int Q, long long K) { root.update(P, Q, K, 0, R - 1); }

long long calculate(int P, int Q, int U, int V) { return root.calculate(P, Q, U, V, 0, R - 1); }

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20