Submission #514273

#	Time	Username	Problem	Language	Result	Execution time	Memory
514273		KoD	Specijacija (COCI20_specijacija)	C++17	110 / 110	3027 ms	77776 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, Q, T;
    std::cin >> N >> Q >> T;
    vector<ll> higher(N + 1);
    for (int i = 0; i <= N; ++i) {
        higher[i] = (ll)i * (i + 1) / 2;
    }
    vector<ll> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
        A[i] -= higher[i] + 1;
    }
    
    struct Node {
        int left, right, size, sum;
        Node() : left(-1), right(-1), size(0), sum(0) {}
    };
    vector<Node> node;

    const auto make_node = [&](const int l, const int r) {
        auto& n = node.emplace_back();
        n.left = l, n.right = r;
        n.size = node[l].size + node[r].size;
        n.sum = node[l].sum + node[r].sum;
        return (int)node.size() - 1;
    };
    
    vector<int> state(N + 1);
    state[N] = RecLambda([&](auto&& dfs, const int n) -> int {
        if (n == 1) {
            auto& n = node.emplace_back();
            n.size = n.sum = 1;
            return (int)node.size() - 1;
        } else {
            return make_node(dfs(n / 2), dfs(n - n / 2));
        }
    })(N);

    const auto get_pos = RecLambda([&](auto&& dfs, const int u, const int k) -> int {
        if (k == 0) return 0;
        if (k == node[u].sum) return node[u].size;
        const int lch = node[u].left;
        if (node[lch].sum <= k) {
            return node[lch].size + dfs(node[u].right, k - node[lch].sum);
        } else {
            return dfs(lch, k);
        }
    });
    
    const auto get_rank = RecLambda([&](auto&& dfs, const int u, const int k) -> int {
        if (k == 0) return 0;
        if (k == node[u].size) return node[u].sum;
        const int lch = node[u].left;
        if (node[lch].size <= k) {
            return node[lch].sum + dfs(node[u].right, k - node[lch].size);
        } else {
            return dfs(lch, k);
        }
    });

    const auto disable = RecLambda([&](auto&& dfs, const int u, const int k) -> int {
        const int lch = node[u].left;
        if (lch == -1) {
            auto& n = node.emplace_back();
            n.size = 1;
            return (int)node.size() - 1;
        } else {
            if (node[lch].sum <= k) {
                return make_node(lch, dfs(node[u].right, k - node[lch].sum));
            } else {
                return make_node(dfs(lch, k), node[u].right);
            }
        }
    });

    for (int i = N - 1; i >= 0; --i) {
        state[i] = disable(state[i + 1], A[i]);
    }
    
    const auto solve = [&](ll x, ll y) {
        int dx = std::upper_bound(higher.begin(), higher.end(), x) - higher.begin() - 1;
        int dy = std::upper_bound(higher.begin(), higher.end(), y) - higher.begin() - 1;
        if (dx > dy) {
            std::swap(x, y);
            std::swap(dx, dy);
        }
        const int u = get_pos(state[dx], x - higher[dx]);
        const int v = get_pos(state[dy], y - higher[dy]);
        int ok = 0, ng = dx + 1;
        while (ng - ok > 1) {
            const int md = (ok + ng) / 2;
            (get_rank(state[md], u) == get_rank(state[md], v) ? ok : ng) = md;
        }
        return higher[ok] + get_rank(state[ok], u);
    };

    const ll mod = (ll)(N + 1) * (N + 2) / 2;
    ll z = 0;
    while (Q--) {
        ll x, y;
        std::cin >> x >> y;
        x -= 1, y -= 1;
        x = (x + T * z) % mod, y = (y + T * z) % mod;
        z = solve(x, y) + 1;
        std::cout << z << '\n';
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60