oj.uz

Submission #514273

# Submission time Handle Problem Language Result Execution time Memory
514273 2022-01-18T06:04:03 Z KoD Specijacija (COCI20_specijacija) C++17
110 / 110
 3027 ms 77776 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 72108 KB Output is correct
2 Correct 13 ms 9124 KB Output is correct
3 Correct 227 ms 72096 KB Output is correct
4 Correct 111 ms 69244 KB Output is correct
5 Correct 218 ms 72076 KB Output is correct
6 Correct 57 ms 35060 KB Output is correct
7 Correct 128 ms 72176 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 72108 KB Output is correct
2 Correct 13 ms 9124 KB Output is correct
3 Correct 227 ms 72096 KB Output is correct
4 Correct 111 ms 69244 KB Output is correct
5 Correct 218 ms 72076 KB Output is correct
6 Correct 57 ms 35060 KB Output is correct
7 Correct 128 ms 72176 KB Output is correct
8 Correct 295 ms 3768 KB Output is correct
9 Correct 265 ms 3556 KB Output is correct
10 Correct 301 ms 3804 KB Output is correct
11 Correct 167 ms 2648 KB Output is correct
12 Correct 312 ms 3776 KB Output is correct
13 Correct 217 ms 3084 KB Output is correct
14 Correct 301 ms 4340 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 72108 KB Output is correct
2 Correct 13 ms 9124 KB Output is correct
3 Correct 227 ms 72096 KB Output is correct
4 Correct 111 ms 69244 KB Output is correct
5 Correct 218 ms 72076 KB Output is correct
6 Correct 57 ms 35060 KB Output is correct
7 Correct 128 ms 72176 KB Output is correct
8 Correct 295 ms 3768 KB Output is correct
9 Correct 265 ms 3556 KB Output is correct
10 Correct 301 ms 3804 KB Output is correct
11 Correct 167 ms 2648 KB Output is correct
12 Correct 312 ms 3776 KB Output is correct
13 Correct 217 ms 3084 KB Output is correct
14 Correct 301 ms 4340 KB Output is correct
15 Correct 3027 ms 76164 KB Output is correct
16 Correct 1400 ms 18296 KB Output is correct
17 Correct 2837 ms 76280 KB Output is correct
18 Correct 1252 ms 18672 KB Output is correct
19 Correct 2841 ms 76256 KB Output is correct
20 Correct 1157 ms 18040 KB Output is correct
21 Correct 2246 ms 77688 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2771 ms 76356 KB Output is correct
2 Correct 2065 ms 38316 KB Output is correct
3 Correct 2803 ms 76292 KB Output is correct
4 Correct 1906 ms 37104 KB Output is correct
5 Correct 2782 ms 76244 KB Output is correct
6 Correct 2016 ms 69364 KB Output is correct
7 Correct 2092 ms 77776 KB Output is correct