oj.uz

Submission #413583

# Submission time Handle Problem Language Result Execution time Memory
413583 2021-05-29T01:39:01 Z KoD Game (IOI13_game) C++17
0 / 100
 2 ms 424 KB 
#include <bits/stdc++.h>
#include "game.h"

using ll = long long;

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

ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

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 = gcd2(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 = gcd2(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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Incorrect 1 ms 292 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Incorrect 1 ms 424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 2 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 2 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -