C - Deciding the Meeting Place Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 人の友人のために集合場所を決めようとしています。友人たちは数直線上にそれぞれ住んでおり、i 番目の友人の現在地は座標 A_i です。

高橋君は、すべての友人がある1つの整数座標 T に集まるようにしたいと考えています。各友人は 1 回の操作で現在の座標を +1 または -1 だけ変化させることができ、この操作を繰り返して目的地 T に到達します。i 番目の友人が T に到達するための移動コストは |A_i - T| 回です。なお、友人の現在地が T と一致する場合、その友人は移動の必要がなく、移動コストは 0 です。

ただし、数直線上には M 個の「立入禁止地点」B_1, B_2, \dots, B_M が設定されています。どの友人も、立入禁止地点に位置することはできません。具体的には、各操作後の座標が立入禁止地点であってはなりません。友人の現在地はいずれも立入禁止地点ではないことが入力として保証されます。また、目的地 T としても立入禁止地点でない座標を選ぶ必要があります。

数直線は1次元であるため、友人の現在地 A_i と目的地 T の間（両端を含まない開区間 (\min(A_i, T),\ \max(A_i, T)) ）に立入禁止地点が1つでも存在する場合、その友人は立入禁止地点を迂回する手段がなく、T に到達することができません。逆に、この区間内に立入禁止地点が1つも存在しない場合、その友人は T に到達可能です。

各友人は独立に移動し、複数の友人が同じ座標に同時に存在しても問題ありません。

高橋君は、すべての友人が到達可能であり、かつ立入禁止地点でない整数座標 T の中から、すべての友人の移動コストの合計 \displaystyle\sum_{i=1}^{N} |A_i - T| が最小となるものを選びたいです。

そのような T が1つ以上存在する場合は、移動コストの合計の最小値を出力してください。すべての友人が到達可能な T が1つも存在しない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • -10^9 \leq B_j \leq 10^9 (1 \leq j \leq M)
  • A_i \neq B_j (1 \leq i \leq N,\ 1 \leq j \leq M)
  • A_i は重複することがある (1 \leq i \leq N)
  • B_j はすべて異なる (1 \leq j \leq M)
  • 入力はすべて整数である

入力

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M
  • 1 行目には、友人の人数を表す整数 N と、立入禁止地点の個数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各友人の現在地を表す整数 A_1, A_2, \dots, A_N が、スペース区切りで与えられる。
  • 3 行目には、立入禁止地点を表す整数 B_1, B_2, \dots, B_M が、スペース区切りで与えられる。ただし M = 0 の場合、3 行目は与えられない。

出力

すべての友人が到達可能な立入禁止地点でない整数座標が存在する場合は、移動コストの合計の最小値を 1 行で出力してください。そのような座標が存在しない場合は -1 を 1 行で出力してください。

入力例 1

3 1
1 2 4
10

出力例 1

3

入力例 2

2 1
0 2
1

出力例 2

-1

入力例 3

10 5
12 15 17 11 19 14 13 16 18 12
-100 10 20 50 100

出力例 3

23

入力例 4

40 15
1020 1500 1800 1100 1999 1300 1700 1600 1400 1250 1750 1900 1050 1150 1350 1450 1550 1650 1850 1950 1200 1280 1320 1380 1420 1480 1520 1580 1620 1680 1720 1780 1820 1880 1920 1980 1010 1090 1110 1890
-1000000000 -5000 0 999 2000 5000 10000 12345 20000 50000 100000 1000000 10000000 100000000 1000000000

出力例 4

10239

入力例 5

1 0
-1000000000

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is trying to decide a meeting place for his N friends. His friends each live on a number line, and the i-th friend is currently at coordinate A_i.

Takahashi wants all friends to gather at a single integer coordinate T. Each friend can change their current coordinate by +1 or -1 in one operation, and repeats this operation to reach the destination T. The movement cost for the i-th friend to reach T is |A_i - T| operations. Note that if a friend's current position coincides with T, that friend does not need to move, and the movement cost is 0.

However, there are M "restricted points" B_1, B_2, \dots, B_M set on the number line. No friend may be located at a restricted point. Specifically, a friend's coordinate after each operation must not be a restricted point. It is guaranteed in the input that no friend's current position is a restricted point. Additionally, the destination T must also be chosen as a coordinate that is not a restricted point.

Since the number line is one-dimensional, if there exists even one restricted point between a friend's current position A_i and the destination T (in the open interval (\min(A_i, T),\ \max(A_i, T))), that friend has no way to bypass the restricted point and cannot reach T. Conversely, if there are no restricted points in this interval, that friend can reach T.

Each friend moves independently, and there is no problem if multiple friends are at the same coordinate simultaneously.

Takahashi wants to choose, among integer coordinates T that are not restricted points and are reachable by all friends, the one that minimizes the total movement cost \displaystyle\sum_{i=1}^{N} |A_i - T|.

If at least one such T exists, output the minimum total movement cost. If no T exists that is reachable by all friends, output -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • -10^9 \leq B_j \leq 10^9 (1 \leq j \leq M)
  • A_i \neq B_j (1 \leq i \leq N,\ 1 \leq j \leq M)
  • A_i may contain duplicates (1 \leq i \leq N)
  • All B_j are distinct (1 \leq j \leq M)
  • All inputs are integers

Input

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M
  • The first line contains an integer N representing the number of friends and an integer M representing the number of restricted points, separated by a space.
  • The second line contains integers A_1, A_2, \dots, A_N representing the current positions of the friends, separated by spaces.
  • The third line contains integers B_1, B_2, \dots, B_M representing the restricted points, separated by spaces. However, if M = 0, the third line is not given.

Output

If there exists an integer coordinate that is not a restricted point and is reachable by all friends, output the minimum total movement cost in one line. If no such coordinate exists, output -1 in one line.

Sample Input 1

3 1
1 2 4
10

Sample Output 1

3

Sample Input 2

2 1
0 2
1

Sample Output 2

-1

Sample Input 3

10 5
12 15 17 11 19 14 13 16 18 12
-100 10 20 50 100

Sample Output 3

23

Sample Input 4

40 15
1020 1500 1800 1100 1999 1300 1700 1600 1400 1250 1750 1900 1050 1150 1350 1450 1550 1650 1850 1950 1200 1280 1320 1380 1420 1480 1520 1580 1620 1680 1720 1780 1820 1880 1920 1980 1010 1090 1110 1890
-1000000000 -5000 0 999 2000 5000 10000 12345 20000 50000 100000 1000000 10000000 100000000 1000000000

Sample Output 4

10239

Sample Input 5

1 0
-1000000000

Sample Output 5

0