Submission #56022411

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <algorithm>
#include <ios>
#include <iostream>
#include <vector>
auto solve() {
    auto n = 0;
    auto q = 0;
    std::cin >> n >> q;
    auto a = std::vector<int>(n);
    for (auto& x : a) {
        std::cin >> x;
    }
    std::sort(std::begin(a), std::end(a));
    for (auto i = 0; i < q; ++i) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <algorithm>
#include <ios>
#include <iostream>
#include <vector>

auto solve() {

    auto n = 0;
    auto q = 0;

    std::cin >> n >> q;

    auto a = std::vector<int>(n);

    for (auto& x : a) {
        std::cin >> x;
    }

    std::sort(std::begin(a), std::end(a));

    for (auto i = 0; i < q; ++i) {
        auto b = 0;
        auto k = 0;
        std::cin >> b >> k;
        auto hi = std::max(b - a[0], a[n - 1] - b) + 1;
        auto lo = -1;
        while (hi - lo > 1) {
            const auto mid = (lo + hi) / 2;
            (
                std::upper_bound(std::begin(a), std::end(a), b + mid) -
                std::lower_bound(std::begin(a), std::end(a), b - mid) < k ?
                lo : hi
            ) = mid;
        }
        std::cout << hi << '\n';
    }

}

auto main() -> int {

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    solve();

    return 0;

}

Submission Info

Judge Result