제출 #769483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
769483		boris_mihov	게임 (IOI13_game)	C++17	80 / 100	2817 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 Node
{
    llong value;
    int l, r;

    Node()
    {
        l = r = value = 0;
    }
};

int cntS;
Node trees[(int)1e7];
struct DynamicSegmentTree2D
{
    struct DynamicSegmentTree
    {
        int root;
        void update(int l, int r, int node, const int &queryPos, const llong &value)
        {
            if (l == r)
            {
                trees[node].value = value;
                return;
            }

            int mid = (l + r) / 2;
            if (queryPos <= mid)
            {
                if (trees[node].l == 0)
                {
                    trees[node].l = cntS++;
                }

                update(l, mid, trees[node].l, queryPos, value);
            } else
            {
                if (trees[node].r == 0)
                {
                    trees[node].r = cntS++;
                }

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

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

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

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

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

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

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

        int l, r;
        DynamicSegmentTree()
        {
            l = r = 0;
        }
    };

    int cnt;
    DynamicSegmentTree tree[(int)2e6];

    DynamicSegmentTree2D()
    {
        cnt = 2;
        cntS = 2;
        tree[1].root = 1;
    }

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

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

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

            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, const int &queryLROW, const int &queryRROW, const int &queryLCOL, const 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