Overview

This problem asks for the “minimum number of speaker activations \(K\)” needed to deliver the required sound volume to all \(N\) booths arranged on a line. By optimally choosing the speaker position \(P\), we minimize the number of activations \(K\).

Analysis

1. Rephrasing the Problem (Reduction to a Decision Problem)

Directly solving “find the minimum number \(K\)” is difficult, but we can consider the decision problem: “When the speaker is activated \(K\) times, does there exist a placement position \(P\) such that sufficient sound volume reaches all booths?”

As the number of activations \(K\) increases, the total volume delivered to each booth increases, making it easier to satisfy the conditions. Using this monotonicity (the property that if achievable with some \(K\), it is always achievable with any larger number), we can find the minimum \(K\) using binary search.

2. Decision Method with Fixed \(K\)

When the number of activations \(K\) is fixed, consider each booth \(i\) (position \(X_i\), threshold \(D_i\)). For the total volume reaching booth \(i\) to be at least \(D_i\), the required volume per activation \(C_i\) must be: $\(C_i = \lceil D_i / K \rceil\)\( (ceiling of \)D_i / K$) or more.

When the speaker is placed at position \(P\), the delivered volume is \(\max(V - |X_i - P|, 0)\), so the condition becomes: $\(\max(V - |X_i - P|, 0) \ge C_i\)$

We find the range of \(P\) that satisfies this: * When \(C_i > V\): Even placing the speaker directly above the booth yields at most volume \(V\), which cannot reach \(C_i\). Therefore, it is impossible to satisfy the condition for any \(P\). * When \(C_i \le V\): $\(V - |X_i - P| \ge C_i \iff |X_i - P| \le V - C_i\)\( Removing the absolute value, the range that the speaker position \)P\( must satisfy is: \)\(X_i - V + C_i \le P \le X_i + V - C_i\)$

For each booth \(i\), we obtain the interval \([L_i, R_i]\) where the speaker should be placed: * \(L_i = X_i - V + C_i\) * \(R_i = X_i + V - C_i\)

3. Determining Existence of \(P\) Satisfying All Booths Simultaneously

For a \(P\) to satisfy the conditions for all booths \(i\) (\(1 \le i \le N\)) simultaneously, there must be a common intersection among all intervals \([L_i, R_i]\) determined by each booth.

The necessary and sufficient condition for the common intersection to exist is: “the maximum of all left endpoints is less than or equal to the minimum of all right endpoints.” That is, if the following inequality holds, an integer \(P\) satisfying the conditions exists: $\(\max_{1 \le i \le N} L_i \le \min_{1 \le i \le N} R_i\)$

This decision can be made in \(O(N)\) by scanning all booths once.

---

Algorithm

1. Setting the Binary Search Range: Set the minimum of \(K\) to low = 1 and the maximum to high = 10^18 (the maximum value of \(D_i\)).
2. Pre-check for Feasibility: If the conditions cannot be satisfied even when \(K\) is sufficiently large (set to high), then it is impossible regardless of speaker placement. In this case, output -1 and terminate.
3. Executing Binary Search: For the midpoint mid of low and high, perform check(mid).
   • If the condition is satisfied: There may be a smaller \(K\) that works, so continue searching with high = mid - 1.
   • If the condition is not satisfied: A larger \(K\) is needed, so set low = mid + 1.
4. Output the Answer: Output the minimum \(K\) obtained from the search.

---

Complexity

• Time Complexity: \(O(N \log(\max D_i))\) The number of binary search iterations is \(\log_2(10^{18}) \approx 60\). Each decision (the check function) scans \(N\) booths, taking \(O(N)\). Therefore, the overall execution time is sufficiently fast and well within the time limit.

• Space Complexity: \(O(N)\) Proportional to the array size needed to store the coordinates \(X_i\) and thresholds \(D_i\) of each booth.

---

Implementation Notes

• Writing ceiling division: The ceiling of \(D_i / K\) (\(\lceil D_i / K \rceil\)) can be written using integer arithmetic as (D[i] + K - 1) / K.

• Overflow prevention: Since \(D_i\) and \(K\) can be as large as \(10^{18}\), long long type must be used in C++. Also, when computing the interval endpoints \(L_i, R_i\), values may temporarily become very large (or very negative), so sufficiently large initial values (such as 4e18) are set.

  Source Code

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

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long V;
    if (!(cin >> N >> V)) return 0;

    vector<long long> X(N), D(N);
    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> D[i];
    }

    // スピーカーを K 回鳴らしたときに条件を満たす設置位置 P が存在するか判定
    auto check = [&](long long K) -> bool {
        long long max_L = -4e18;
        long long min_R = 4e18;
        for (int i = 0; i < N; ++i) {
            // C_i = ceil(D[i] / K)
            long long C_i = (D[i] + K - 1) / K;
            if (C_i > V) return false;
            long long L_i = X[i] - V + C_i;
            long long R_i = X[i] + V - C_i;
            max_L = max(max_L, L_i);
            min_R = min(min_R, R_i);
        }
        return max_L <= min_R;
    };

    long long low = 1, high = 1e18;
    // K をいくら大きくしても（C_i = 1 にしても）条件を満たせない場合は -1
    if (!check(high)) {
        cout << -1 << "\n";
        return 0;
    }

    // 二分探索で最小の K を求める
    long long ans = high;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.