Submission #413586

#	Time	Username	Problem	Language	Result	Execution time	Memory
413586		KoD	Game (IOI13_game)	C++17	0 / 100	2 ms	332 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using ll = long long;

template <class T> using Vec = std::vector<T>;

int Row, Column;

struct SegGCD {
    struct Node {
        ll gcd;
        int left, right;
        std::array<int, 2> ch;
        Node(const int left, const int right): gcd(0), left(left), right(right), ch({-1, -1}) {}
    };

    Vec<Node> node;

    SegGCD() {
        node.emplace_back(0, Column);
    }

    void fetch(const int u) {
        const int l = node[u].ch[0];
        const int r = node[u].ch[1];
        node[u].gcd = std::gcd(l == -1 ? 0 : node[l].gcd, r == -1 ? 0 : node[r].gcd);
    }

    void assign(const int x, const ll v) {
        int u = 0;
        Vec<int> path;
        while (node[u].right - node[u].left > 1) {
            path.push_back(u);
            const int mid = (node[u].left + node[u].right) / 2;
            if (x < mid) {
                if (node[u].ch[0] == -1) {
                    node.emplace_back(node[u].left, mid);
                    node[u].ch[0] = (int) node.size() - 1;
                }
                u = node[u].ch[0];
            }
            else {
                if (node[u].ch[1] == -1) {
                    node.emplace_back(mid, node[u].right);
                    node[u].ch[1] = (int) node.size() - 1;
                }
                u = node[u].ch[1];
            }
        }
        node[u].gcd = v;
        while (!path.empty()) {
            fetch(path.back());
            path.pop_back();
        }
    }

    void fold(const int u, const int l, const int r, ll& base) {
        if (u == -1 or node[u].right <= l or r <= node[u].left) {
            return;
        }
        if (l <= node[u].left and node[u].right <= r) {
            base = std::gcd(base, node[u].gcd);
            return;
        }
        fold(node[u].ch[0], l, r, base);
        fold(node[u].ch[1], l, r, base);
    }
};

struct Seg2D {
    struct Node {
        SegGCD seg;
        int left, right;
        std::array<int, 2> ch;
        Node(const int left, const int right) : seg(), left(left), right(right), ch({-1, -1}) {}
    };
    
    Vec<Node> node;

    Seg2D() {
        node.emplace_back(0, Row);
    }

    void assign(const int x, const int y, const ll v) {
        int u = 0;
        while (node[u].right - node[u].left > 1) {
            node[u].seg.assign(y, v);
            const int mid = (node[u].left + node[u].right) / 2;
            if (x < mid) {
                if (node[u].ch[0] == -1) {
                    node.emplace_back(node[u].left, mid);
                    node[u].ch[0] = (int) node.size() - 1;
                }
                u = node[u].ch[0];
            }
            else {
                if (node[u].ch[1] == -1) {
                    node.emplace_back(mid, node[u].right);
                    node[u].ch[1] = (int) node.size() - 1;
                }
                u = node[u].ch[1];
            }
        }
        node[u].seg.assign(y, v);
    }

    void fold(const int u, const int l, const int r, const int l2, const int r2, ll& base) {
        if (u == -1 or node[u].right <= l or r <= node[u].left) {
            return;
        }
        if (l <= node[u].left and node[u].right <= r) {
            node[u].seg.fold(0, l2, r2, base);
            return;
        }
        fold(node[u].ch[0], l, r, l2, r2, base);
        fold(node[u].ch[1], l, r, l2, r2, base);
    }
};

Seg2D seg;

void init(int R, int C) {
    Row = R;
    Column = C;
    seg = Seg2D();
}

void update(int P, int Q, ll K) {
    seg.assign(P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    ll base = 0;
    seg.fold(0, P, U + 1, Q, V + 1, base);
    return base;
}

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