/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
数直線上に N 枚の布があります。 i 枚目 (1\le i\le N) の布は数直線上の区間 \lbrack L _ i,R _ i\rbrack を覆っています。 数直線上の点は 2 枚以上の布で覆われていることも、どの布にも覆われていないこともあります。
2 枚の布が重なっているとは、数直線上のある点がその 2 枚の布どちらにも覆われていることをいいます。
重なっていない 2 枚の布について、それらの距離を以下のように定めます。
- 一方の布に覆われている点 p ともう一方の布に覆われている点 q に対する |p-q| の最小値
どの 2 枚も重なっていない K 枚の布に対して、そのスコアを布どうしの距離の最小値と定めます。 N 枚の布からどの 2 枚も重なっていないように K 枚を選ぶときのスコアの最大値を求めてください。
ただし、そのように K 枚の布を選ぶことができない場合、-1 を出力してください。
制約
- 2\le K\le N\le2\times10 ^ 5
- 0\le L _ i\lt R _ i\le10 ^ 9\ (1\le i\le N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K L _ 1 R _ 1 L _ 2 R _ 2 \vdots L _ N R _ N
出力
答えを出力せよ。
入力例 1
6 3 1 12 2 7 5 9 9 13 10 18 15 20
出力例 1
2
2 枚目、4 枚目、6 枚目の布を選ぶと、これらはどの 2 枚も重なっていません。 2 枚目の布と 4 枚目の布の距離は 2 、2 枚目の布と 6 枚目の布の距離は 8 、4 枚目の布と 6 枚目の布の距離は 2 なので、この選び方のスコアは 2 です。
スコアが 3 以上になるように 3 枚の布を選ぶことはできないため、2 を出力してください。
入力例 2
2 2 1 5 5 9
出力例 2
-1
与えられた 2 枚の布は重なっているので、どの 2 枚も重なっていないように 2 枚の布を選ぶことはできません。
よって、-1 を出力してください。
1 枚目の布と 2 枚目の布は一点 5 でのみ重なっていることに注意してください。
入力例 3
20 5 169 748 329 586 529 972 432 520 408 587 138 250 114 656 299 632 755 984 404 772 155 506 832 854 353 465 374 387 384 567 555 631 428 951 104 705 405 530 102 258
出力例 3
35
Score : 400 points
Problem Statement
There are N cloths on a number line. The i-th (1\le i\le N) cloth covers the interval \lbrack L _ i,R _ i\rbrack on the line. A point on the line may be covered by two or more cloths, or not covered by any cloth.
Two cloths are said to overlap if some point on the line is covered by both of those cloths.
For two cloths that do not overlap, define their distance as follows:
- The minimum value of |p-q| over all points p covered by one cloth and all points q covered by the other cloth.
For K cloths no two of which overlap, define their score as the minimum distance among all pairs of those cloths. Find the maximum possible score when choosing K cloths from the N cloths so that no two of the chosen cloths overlap.
If it is impossible to choose K such cloths, output -1.
Constraints
- 2\le K\le N\le2\times10 ^ 5
- 0\le L _ i\lt R _ i\le10 ^ 9\ (1\le i\le N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K L _ 1 R _ 1 L _ 2 R _ 2 \vdots L _ N R _ N
Output
Output the answer.
Sample Input 1
6 3 1 12 2 7 5 9 9 13 10 18 15 20
Sample Output 1
2
Choosing the second, fourth, and sixth cloths, no two of these overlap. The distance between the second and fourth cloths is 2, the distance between the second and sixth cloths is 8, and the distance between the fourth and sixth cloths is 2, so the score of this choice is 2.
It is impossible to choose three cloths with a score of 3 or more, so output 2.
Sample Input 2
2 2 1 5 5 9
Sample Output 2
-1
The given two cloths overlap, so it is impossible to choose two cloths so that no two overlap.
Thus, output -1.
Note that the first and second cloths overlap only at the single point 5.
Sample Input 3
20 5 169 748 329 586 529 972 432 520 408 587 138 250 114 656 299 632 755 984 404 772 155 506 832 854 353 465 374 387 384 567 555 631 428 951 104 705 405 530 102 258
Sample Output 3
35