Submission #870928

#	Time	Username	Problem	Language	Result	Execution time	Memory
870928		normankr07	Game (IOI13_game)	C++17	100 / 100	1981 ms	81972 KiB

game

#pragma GCC optimize("Ofast,unroll-loops,inline")
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = int64_t;
#define int int64_t
#define MAXR 1e9
#define MAXC 1e9

long long gcd2(long long X, long long Y)
{
    if (X == 0 || Y == 0)
    {
        return X + Y;
    }

    long long tmp;
    while (X != Y && Y != 0)
    {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct l2_node
{
    int ml, mr;
    l2_node *lft, *rht;
    ll val;
    l2_node(int l, int r) : ml(l), mr(r), lft(NULL), rht(NULL), val(1) {}
};

struct l1_node
{
    l1_node *lft, *rht;
    l2_node l2;
    l1_node() : lft(NULL), rht(NULL), l2(0, MAXC) {}
};

static l1_node root;

static void update2(l2_node *node, int q, int k)
{
    int tl = node->ml, tr = node->mr;
    // Update leaf node
    int tm = (tl + tr) >> 1;
    if (tl + 1 == tr)
    {
        node->val = k;
        return;
    }
    l2_node *&curt = (q < tm) ? node->lft : node->rht;
    if (curt == NULL)
    {
        // Make new leaf node, contain the query value
        curt = new l2_node(q, q + 1);
        curt->val = k;
    }
    else if (curt->ml <= q && q < curt->mr)
    {
        // If the node already exist and contain our query point, do update
        update2(curt, q, k);
    }
    else
    {
        // Travese until the half contain the query node and current node differ;
        do
        {
            (q < tm ? tr : tl) = tm;
            tm = (tl + tr) >> 1;
        } while ((q < tm) == (curt->ml < tm));

        // Make new node and continue to update
        l2_node *nnd = new l2_node(tl, tr);
        (curt->ml < tm ? nnd->lft : nnd->rht) = curt;
        curt = nnd;
        update2(nnd, q, k);
    }

    node->val = gcd2((node->lft ? node->lft->val : 0),
                     (node->rht ? node->rht->val : 0));
}

ll query2(l2_node *node, int l, int r)
{
    if (node == NULL || r <= node->ml || node->mr <= l)
        return 0;
    else if (l <= node->ml && node->mr <= r)
        return node->val;
    return gcd2(query2(node->lft, l, r), query2(node->rht, l, r));
}

static void update1(l1_node *node, int l, int r,
                    int p, int q, int k)
{
    int tm = (l + r) >> 1;
    if (l + 1 == r)
        update2(&node->l2, q, k);
    else
    {
        l1_node *&curt = p < tm ? node->lft : node->rht;
        (p < tm ? r : l) = tm;
        if (curt == NULL)
            curt = new l1_node();
        update1(curt, l, r, p, q, k);
        k = gcd2((node->lft ? query2(&node->lft->l2, q, q + 1) : 0),
                 (node->rht ? query2(&node->rht->l2, q, q + 1) : 0));
        update2(&node->l2, q, k);
    }
}

int query1(l1_node *node, int l, int r, int ax, int ay, int bx, int by)
{
    if (node == NULL || ay <= l || r <= ax)
        return 0;
    else if (ax <= l && r <= ay)
        return query2(&node->l2, bx, by);
    int tm = (l + r) >> 1;
    return gcd2(query1(node->lft, l, tm, ax, ay, bx, by),
                query1(node->rht, tm, r, ax, ay, bx, by));
}

#undef int

// Original Function
void init(int R, int C)
{
}

void update(int P, int Q, long long K)
{
    update1(&root, 0, MAXR, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    return query1(&root, 0, MAXR, P, U + 1, Q, V + 1);
    // return 42;
}

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