Overview

This problem asks for the minimum total distance traveled when gathering \(N\) friends on a number line to a single coordinate \(T\). However, movement that crosses a forbidden point \(B\) or staying at a forbidden point is not allowed.

Analysis

1. Impact of Forbidden Points on Movement

Let \(A_{\min}\) be the initial coordinate of the leftmost friend and \(A_{\max}\) be the initial coordinate of the rightmost friend.

If there exists even one forbidden point \(B_j\) within the open interval \((A_{\min}, A_{\max})\), then no matter what destination \(T\) is chosen, it is impossible for everyone to gather. - If the destination \(T\) is to the left of \(B_j\) (\(T < B_j\)), the rightmost person (\(A_{\max} > B_j\)) cannot cross \(B_j\) to move left. - If the destination \(T\) is to the right of \(B_j\) (\(T > B_j\)), the leftmost person (\(A_{\min} < B_j\)) cannot cross \(B_j\) to move right. - Setting the destination \(T\) itself to \(B_j\) is also impossible since it is a forbidden point.

Therefore, if even one forbidden point is contained in the open interval \((A_{\min}, A_{\max})\), we can immediately output -1.

2. When No Forbidden Points Exist in the Interval

Consider the case where no forbidden points are contained in the open interval \((A_{\min}, A_{\max})\). In this case, there are no forbidden points in the closed interval \([A_{\min}, A_{\max}]\) (since it is guaranteed that the initial coordinates \(A_i\) of friends are not forbidden points, the endpoints are also not forbidden points).

Therefore, any integer coordinate \(T\) within this interval can be chosen as the destination, and all friends can reach \(T\) without being blocked by forbidden points.

3. Minimizing the Cost

Without considering obstacles, it is mathematically known that the \(T\) that minimizes the total distance \(\displaystyle\sum_{i=1}^{N} |A_i - T|\) is the median of \(A\). When \(A\) is sorted in ascending order, the median \(T = A[N / 2]\) is always located within the range \([A_{\min}, A_{\max}]\).

From the earlier analysis, since there are no forbidden points in the interval \([A_{\min}, A_{\max}]\), this median \(T\) is always valid as a destination. Therefore, the optimal solution can be obtained simply by choosing the median \(T\) of \(A\) and calculating the total cost at that point.

Algorithm

1. Sort the coordinate array \(A\) of friends and the forbidden points array \(B\) in ascending order.
2. Obtain the minimum value \(A_{\min} = A[0]\) and maximum value \(A_{\max} = A[N-1]\) of \(A\).
3. Using binary search (C++’s std::upper_bound), determine whether any element of \(B\) exists within the open interval \((A_{\min}, A_{\max})\).
   • Specifically, check whether the smallest element of \(B\) greater than \(A_{\min}\) is less than \(A_{\max}\).
   • If such an element exists, it is impossible for everyone to gather, so output -1 and terminate.
4. If no such element exists, set the destination \(T\) to the median of \(A\): \(T = A[N/2]\).
5. Calculate and output the total distance from each friend to \(T\): \(\displaystyle\sum_{i=1}^{N} |A_i - T|\).

Complexity

• Time Complexity: \(O(N \log N + M \log M)\)
  • Sorting array \(A\) takes \(O(N \log N)\), and sorting array \(B\) takes \(O(M \log M)\).
  • Binary search (upper_bound) takes \(O(\log M)\).
  • Computing the total cost takes \(O(N)\).
  • Overall, sorting is the bottleneck, which comfortably fits within the time limit.
• Space Complexity: \(O(N + M)\)
  • Memory is needed to store the input arrays \(A\) and \(B\).

Implementation Notes

• Overflow Caution Since the absolute value of coordinates can be up to \(10^9\) and the number of people \(N\) can be up to \(2 \times 10^5\), the total movement cost can reach approximately \(2 \times 10^{14}\). This overflows a 32-bit integer type (int), so a 64-bit integer type (long long in C++) must be used for computing costs and storing the total sum.

• Open Interval Check Whether there exists an element of \(B\) satisfying the open interval condition “greater than \(A_{\min}\) and less than \(A_{\max}\)” can be smartly determined in \(O(\log M)\) using std::upper_bound.

  Source Code

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

using namespace std;

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

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

    vector<long long> B(M);
    for (int i = 0; i < M; ++i) {
        cin >> B[i];
    }

    // Sort both arrays to enable binary search and median finding
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    long long min_A = A.front();
    long long max_A = A.back();

    // Check if there is any forbidden point B_j strictly between min_A and max_A
    auto it = upper_bound(B.begin(), B.end(), min_A);
    if (it != B.end() && *it < max_A) {
        cout << -1 << "\n";
        return 0;
    }

    // The optimal meeting point T is the median of A
    long long T = A[N / 2];
    long long total_cost = 0;
    for (int i = 0; i < N; ++i) {
        total_cost += abs(A[i] - T);
    }

    cout << total_cost << "\n";

    return 0;
}

---

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