제출 #769464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
769464		boris_mihov	Game (IOI13_game)	C++17	80 / 100	2762 ms	256000 KiB

game

#include "game.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXQ = 250000 + 10;
const int MAXU = 22000 + 10;

llong gcd(llong x, llong y)
{
    if (x == 0) return y;
    if (y == 0) return x;
    while (y != 0)
    {
        x %= y;
        x ^= y;
        y ^= x;
        x ^= y;
    }

    return x;
}

int R, C;
struct DynamicSegmentTree2D
{
    struct DynamicSegmentTree
    {
        struct Node
        {
            llong value;
            int l, r;

            Node()
            {
                l = r = value = 0;
            }
        };
        
        int cnt;
        std::vector <Node> tree;

        void update(int l, int r, int node, int queryPos, llong value)
        {
            if (l == r)
            {
                tree[node].value = value;
                return;
            }

            int mid = (l + r) / 2;
            if (queryPos <= mid)
            {
                if (tree[node].l == 0)
                {
                    Node newNode;
                    tree.push_back(newNode);
                    tree[node].l = cnt++;
                }

                update(l, mid, tree[node].l, queryPos, value);
            } else
            {
                if (tree[node].r == 0)
                {
                    Node newNode;
                    tree.push_back(newNode);
                    tree[node].r = cnt++;
                }

                update(mid + 1, r, tree[node].r, queryPos, value);
            }

            tree[node].value = gcd(tree[tree[node].l].value, tree[tree[node].r].value);
        }

        llong query(int l, int r, int node, int queryL, int queryR)
        {
            if (node == 0 || r < queryL || queryR < l)
            {
                return 0;
            }

            if (queryL <= l && r <= queryR)
            {
                return tree[node].value;
            }

            int mid = (l + r) / 2;
            return gcd(query(l, mid, tree[node].l, queryL, queryR), query(mid + 1, r, tree[node].r, queryL, queryR));
        }

        void update(int pos, llong value)
        {
            update(1, C, 1, pos, value);
        }

        llong query(int l, int r)
        {
            return query(1, C, 1, l, r);
        }

        int l, r;
        DynamicSegmentTree()
        {
            cnt = 2;
            Node newNode;
            tree.push_back(newNode);
            tree.push_back(newNode);
            l = r = 0;
        }
    };

    int cnt;
    std::vector <DynamicSegmentTree> tree;

    DynamicSegmentTree2D()
    {
        cnt = 2;
        DynamicSegmentTree newNode;
        tree.push_back(newNode);
        tree.push_back(newNode);
    }

    void update(int l, int r, int node, int queryROW, int queryCOL, llong value)
    {
        if (l == r)
        {
            tree[node].update(queryCOL, value);
            return;
        }

        int mid = (l + r) / 2;
        if (queryROW <= mid)
        {
            if (tree[node].l == 0)
            {
                DynamicSegmentTree newNode;
                tree.push_back(newNode);
                tree[node].l = cnt++;
            }

            update(l, mid, tree[node].l, queryROW, queryCOL, value);
        } else
        {
            if (tree[node].r == 0)
            {
                DynamicSegmentTree newNode;
                tree.push_back(newNode);
                tree[node].r = cnt++;
            }

            update(mid + 1, r, tree[node].r, queryROW, queryCOL, value);
        }

        llong newVal = 0;
        if (tree[node].l != 0)
        {
            newVal = tree[tree[node].l].query(queryCOL, queryCOL);
        }

        if (tree[node].r != 0)
        {
            newVal = gcd(newVal, tree[tree[node].r].query(queryCOL, queryCOL));
        }

        tree[node].update(queryCOL, newVal);
    }

    llong query(int l, int r, int node, int queryLROW, int queryRROW, int queryLCOL, int queryRCOL)
    {
        if (node == 0 || r < queryLROW || queryRROW < l)
        {
            return 0;
        }

        if (queryLROW <= l && r <= queryRROW)
        {
            return tree[node].query(queryLCOL, queryRCOL);
        }

        int mid = (l + r) / 2;
        return gcd(query(l, mid, tree[node].l, queryLROW, queryRROW, queryLCOL, queryRCOL),
                   query(mid + 1, r, tree[node].r, queryLROW, queryRROW, queryLCOL, queryRCOL));
    }

    void update(int row, int col, llong value)
    {
        update(1, R, 1, row, col, value);
    }

    llong query(int rowL, int colL, int rowR, int colR)
    {
        return query(1, R, 1, rowL, rowR, colL, colR);
    }
};

DynamicSegmentTree2D tree;
void init(int _R, int _C) 
{
    R = _R;
    C = _C;
    /* ... */
}

void update(int P, int Q, long long K) 
{
    P++; Q++;
    tree.update(P, Q, K);
}

llong calculate(int P, int Q, int U, int V) 
{
    P++; Q++; U++; V++;
    return tree.query(P, Q, U, V);
}

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