Overview

This problem asks for the minimum total movement cost (sum of distances) when \(N\) friends on a number line gather at a single coordinate \(T\) while avoiding restricted points \(B\).

Analysis

1. Conditions on the Range Each Friend Can Move

When each friend \(i\) moves from their initial coordinate \(A_i\) to the destination \(T\), there must be no restricted points between them (excluding the endpoints). This can be rephrased as: “Every friend cannot leave the ‘interval bounded by restricted points’ in which they initially exist.”

Therefore, for each \(A_i\), if we let \(L_i\) and \(R_i\) denote the nearest restricted points to the left and right respectively, the range of coordinates \(T\) that friend \(i\) can reach is: $\(L_i < T < R_i \iff L_i + 1 \leq T \leq R_i - 1\)$

2. Determining the Range Reachable by Everyone

For all friends to gather at the same coordinate \(T\), the above condition must be satisfied for all \(i\). In other words, the required range \([P, Q]\) for \(T\) is the intersection of all friends’ reachable ranges. - \(P = \max_{1 \leq i \leq N} (L_i) + 1\) - \(Q = \min_{1 \leq i \leq N} (R_i) - 1\)

If \(P > Q\), then no coordinate \(T\) exists where everyone can gather, and the answer is \(-1\).

3. Determining \(T\) to Minimize Cost

When a valid range \([P, Q]\) exists where everyone can gather, we search for \(T\) within this range that minimizes the total movement cost \(f(T) = \sum_{i=1}^{N} |A_i - T|\).

In general, the sum of absolute values \(f(T)\) is a convex function (convex downward), and without constraints, its minimum is achieved at the median of \(A\). When \(A\) is sorted in ascending order, let the median be \(M = A[\lfloor (N-1)/2 \rfloor]\) (the middle element when \(N\) is odd, or any value between the two middle elements when \(N\) is even).

Due to the properties of convex functions, the \(T\) that minimizes \(f(T)\) within the range \([P, Q]\) is the median \(M\) clipped to the range \([P, Q]\). $\(T = \max(P, \min(Q, M))\)$

4. Efficient Cost Calculation

Once the optimal \(T\) is determined, we calculate the total cost \(\sum_{i=1}^{N} |A_i - T|\). A naive calculation takes \(O(N)\), but by sorting \(A\) in advance and computing prefix sums, we can calculate it in \(O(\log N)\) using binary search.

If \(k\) is the number of \(A_i\) values less than or equal to \(T\), the cost can be decomposed as: $\(\sum_{i=1}^{N} |A_i - T| = \sum_{A_i < T} (T - A_i) + \sum_{A_i \geq T} (A_i - T)\)\( Using the prefix sum \)S\(, this simplifies to a formula computable in \)O(1)\(: \)\(\text{Cost} = T \times (2k - N) + S[N] - 2S[k]\)$

---

Algorithm

1. Initial Processing:

   • Sort the friends’ coordinates \(A\) in ascending order.
   • Sort the restricted points \(B\), and add sufficiently large values (\(-\infty, \infty\)) as sentinels at both ends to simplify boundary handling.

2. Computing the Reachable Range \([P, Q]\):

   • For each \(A_i\), use binary search (bisect_left) to find the nearest restricted points \(L_i\) and \(R_i\) to its left and right.
   • Update \(P = \max(L_i) + 1\) and \(Q = \min(R_i) - 1\).
   • ※ To avoid performing binary search multiple times for the same \(A_i\), processing only unique values of \(A\) (after removing duplicates) provides a constant factor speedup.

3. Feasibility Check:

   • If \(P > Q\), it is impossible to gather, so output -1 and terminate.

4. Determining the Optimal \(T\) and Computing Cost:

   • Find the median \(M = A[(N-1)//2]\) and determine the optimal \(T = \max(P, \min(Q, M))\).
   • Build the prefix sum of \(A\), use binary search to find the insertion position \(k\) of \(T\), compute the cost, and output it.

---

Complexity

• Time Complexity: \(O(N \log N + M \log M)\)

  • Sorting \(A\): \(O(N \log N)\)
  • Sorting \(B\): \(O(M \log M)\)
  • Binary search on \(B\) for each \(A_i\): \(O(N \log M)\)
  • Building prefix sums: \(O(N)\)
  • Determining optimal \(T\) and computing cost: \(O(\log N)\)
  • Overall, sorting and binary search are the bottleneck, which comfortably fits within the time limit.

• Space Complexity: \(O(N + M)\)

  • Memory proportional to the input size is used to store sorted arrays and prefix sum arrays.

---

Implementation Notes

• Adding Sentinels: By adding -INF and INF to both ends of the restricted points array \(B\), we can handle cases where “a friend is to the left (or right) of all restricted points” uniformly without special boundary handling.

• Speedup Through Duplicate Removal: When multiple friends are at the same coordinate, a single search for \(L_i, R_i\) at that coordinate suffices. By using a set to remove duplicates before performing binary search, we eliminate redundant computations.

  Source Code

import sys
from bisect import bisect_left
from itertools import accumulate

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    A = [int(x) for x in input_data[2:2+N]]
    B = [int(x) for x in input_data[2+N:2+N+M]]
    
    A.sort()
    
    INF = 10**15
    B_sorted = [-INF] + sorted(B) + [INF]
    
    L_max = -INF
    R_min = INF
    
    # A の重複を削除して二分探索の回数を減らす
    A_unique = sorted(list(set(A)))
    for a in A_unique:
        idx = bisect_left(B_sorted, a)
        L = B_sorted[idx-1]
        R = B_sorted[idx]
        if L > L_max:
            L_max = L
        if R < R_min:
            R_min = R
            
    P = L_max + 1
    Q = R_min - 1
    
    if P > Q:
        print(-1)
        return
    
    mid_val = A[(N - 1) // 2]
    T = max(P, min(Q, mid_val))
    
    S = [0] + list(accumulate(A))
    
    idx_T = bisect_left(A, T)
    
    ans = T * (2 * idx_T - N) + S[N] - 2 * S[idx_T]
    print(ans)

if __name__ == '__main__':
    solve()

---

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