Submission #937956

#	Time	Username	Problem	Language	Result	Execution time	Memory
937956		Muaath_5	Game (IOI13_game)	C++17	100 / 100	2769 ms	88232 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;

    int a, b;

    long long g;


    NodeY(int a_, int b_) { a = a_, b = b_; }


    void update(int Q, long long K)

    {

        if (a == b)

        {

            g = K;

            return;

        }


        if (l && 2 * (l->b - l->a + 1) != b - a + 1)

        {

            unique_ptr<NodeY> y = move(l);

            l = make_unique<NodeY>(a, (a + b) / 2);

            (y->b <= (l->a + l->b) / 2 ? l->l : l->r) = move(y);

        }

        if (r && 2 * (r->b - r->a + 1) != b - a + 1)

        {

            unique_ptr<NodeY> y = move(r);

            r = make_unique<NodeY>((a + b) / 2 + 1, b);

            (y->b <= (r->a + r->b) / 2 ? r->l : r->r) = move(y);

        }


        if (Q <= (a + b) / 2)

            (l ? l : l = make_unique<NodeY>(a, (a + b) / 2))->update(Q, K);

        else

            (r ? r : r = make_unique<NodeY>((a + b) / 2 + 1, b))->update(Q, K);


        if (l && (!l->l ^ !l->r))

            l = move(l->l ? l->l : l->r);

        if (r && (!r->l ^ !r->r))

            r = move(r->l ? r->l : r->r);

        g = gcd(l ? l->g : 0, r ? r->g : 0);

    }


    long long calculate(int Q, int V)

    {

        if (b < Q || a > V)

            return 0;

        if (Q <= a && b <= V)

            return g;

        return gcd(l ? l->calculate(Q, V) : 0, r ? r->calculate(Q, V) : 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>(0, C - 1);

        if (A == B)

        {

            y->update(Q, K);

            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,

                         r && r->y ? r->y->calculate(Q, Q) : 0));

    }


    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;

        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: 17 / 17
• Subtask 5: 20 / 20