Submission #722415

#	Time	Username	Problem	Language	Result	Execution time	Memory
722415		finn__	Game (IOI13_game)	C++17	63 / 100	2682 ms	256000 KiB

game

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

#pragma GCC optimize("Os")

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

struct NodeX
{
    int xChildren, yRoot;
};

struct NodeY
{
    int yLeft, yRight;
    long long g;
};

NodeX *root;

int allocNode(size_t s) { return (int)((char *)calloc(1, s) - (char *)root); }

char *getPtr(int offset) { return ((char *)root + offset); }

long long calculateY(int Q, int V, NodeY *z, int A, int B)
{
    if (B < Q || A > V)
        return 0;
    if (Q <= A && B <= V)
        return z->g;
    long long g = 0;
    if (z->yLeft)
        g = gcd(g, calculateY(Q, V, (NodeY *)getPtr(z->yLeft), A, (A + B) / 2));
    if (z->yRight)
        g = gcd(g, calculateY(Q, V, (NodeY *)getPtr(z->yRight), (A + B) / 2 + 1, B));
    return g;
}

long long calculateX(int P, int Q, int U, int V, NodeX *z, int A, int B)
{
    if (B < P || A > U)
        return 0;
    if (P <= A && B <= U)
        return z->yRoot ? calculateY(Q, V, (NodeY *)getPtr(z->yRoot), 0, C - 1) : 0;
    if (z->xChildren)
        return gcd(calculateX(P, Q, U, V, (NodeX *)getPtr(z->xChildren), A, (A + B) / 2),
                   calculateX(P, Q, U, V, (NodeX *)getPtr(z->xChildren) + 1, (A + B) / 2 + 1, B));
    return 0;
}

void updateY(int Q, long long K, NodeY *z, int A, int B)
{
    if (A == B)
    {
        z->g = K;
        return;
    }
    if (Q <= (A + B) / 2)
    {
        if (!z->yLeft)
            z->yLeft = allocNode(sizeof(NodeY));
        updateY(Q, K, (NodeY *)getPtr(z->yLeft), A, (A + B) / 2);
    }
    else
    {
        if (!z->yRight)
            z->yRight = allocNode(sizeof(NodeY));
        updateY(Q, K, (NodeY *)getPtr(z->yRight), (A + B) / 2 + 1, B);
    }
    z->g = gcd(z->yLeft ? ((NodeY *)getPtr(z->yLeft))->g : 0,
               z->yRight ? (((NodeY *)getPtr(z->yRight))->g) : 0);
}

void updateX(int P, int Q, long long K, NodeX *z, int A, int B)
{
    if (!z->yRoot)
        z->yRoot = allocNode(sizeof(NodeY));
    if (A == B)
    {
        updateY(Q, K, (NodeY *)getPtr(z->yRoot), 0, C - 1);
        return;
    }
    if (!z->xChildren)
        z->xChildren = allocNode(2 * sizeof(NodeX));
    if (P <= (A + B) / 2)
        updateX(P, Q, K, (NodeX *)getPtr(z->xChildren), A, (A + B) / 2);
    else
        updateX(P, Q, K, (NodeX *)getPtr(z->xChildren) + 1, (A + B) / 2 + 1, B);
    long long g = 0;
    if (((NodeX *)getPtr(z->xChildren))->yRoot)
        g = gcd(g, calculateY(Q, Q, (NodeY *)getPtr(((NodeX *)getPtr(z->xChildren))->yRoot), 0, C - 1));
    if ((((NodeX *)getPtr(z->xChildren)) + 1)->yRoot)
        g = gcd(g, calculateY(Q, Q, (NodeY *)getPtr(((NodeX *)getPtr(z->xChildren) + 1)->yRoot), 0, C - 1));
    updateY(Q, g, (NodeY *)getPtr(z->yRoot), 0, C - 1);
}

void init(int R, int C) { root = (NodeX *)calloc(1, sizeof *root); }

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

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

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