D - Accomplice Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

とある館で殺人事件が起きました。犯人の候補は N 人おり、彼らを人 1、人 2、\dots、人 N と呼びます。

人 i は時刻 S_i に館に入り、時刻 T_i に館を出て、ほかの時刻には出入りしませんでした。

犯行について以下のことが分かっています。

  • 犯人はちょうど 2 人いる。
  • 犯行はある整数時刻 x に開始し、D 単位時間かけて行われ、時刻 x + D に完了した。
  • 犯人は 2 人とも犯行開始から犯行完了まで常に館にいた。（犯行開始と同時に館に入ったり、犯行完了と同時に館を出たりしたかもしれない。）

N 人の犯人候補の中に犯人が 2 人ともいると仮定したとき、2 人の犯人と犯行開始時刻の組としてありうるものは何通りあるでしょうか。ここで、2 人の犯人には順番を付けません。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq S_i \leq T_i \leq 10^6
  • 1 \leq D \leq 10^6
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N D
S_1 T_1
S_2 T_2
\vdots
S_N T_N

出力

2 人の犯人と犯行開始時刻の組としてありうるものの個数を出力せよ。

入力例 1

3 2
9 17
10 12
13 20

出力例 1

4

この例では犯人の候補が 3 人おり、犯行は 2 単位時間かけて行われました。

  • 人 1, 2 が犯人であるとすると、彼らがともに館にいたのは時刻 10 から時刻 12 までです。犯行開始時刻が時刻 10 であるとすると、2 単位時間かけて犯行が可能です。
  • 人 1, 3 が犯人であるとすると、彼らがともに館にいたのは時刻 13 から時刻 17 までです。犯行開始時刻が時刻 13, 14, 15 のいずれかであるとすると、2 単位時間かけて犯行が可能です。
  • 人 2, 3 が犯人であるとすると、彼らがともに館にいた時間はなく、このペアによる犯行は不可能です。

以上より、2 人の犯人と犯行開始時刻の組としてありうるものは（人 1, 2, 時刻 10）、（人 1, 3, 時刻 13）、（人 1, 3, 時刻 14）、（人 1, 3, 時刻 15）の 4 通りです。

入力例 2

3 5
9 17
10 12
13 20

出力例 2

0

犯人の候補は入力例 1 と同じですが、今回の犯行は 5 単位時間かけて行われました。

どの 2 人が犯人であるとしても、2 人がともに館にいた時間が犯行の所要時間より短く、犯行は不可能です。

従って、2 人の犯人と犯行開始時刻の組としてありうるものは 0 通りです。（すなわち、仮定は誤りであり、我々は真犯人を逃しています。）

入力例 3

4 1
1 1000000
1 1000000
1 1000000
1 1000000

出力例 3

5999994

より大きなケースでのオーバーフローに注意してください。

Score : 400 points

Problem Statement

A murder occurred at a certain mansion. There are N suspects, called person 1, person 2, \dots, person N.

Person i entered the mansion at time S_i, left the mansion at time T_i, and did not enter or leave at any other times.

The following facts are known about the crime:

  • There are exactly two culprits.
  • The crime started at some integer time x, took D units of time, and was completed at time x + D.
  • Both culprits were in the mansion at all times from the start to the completion of the crime. (They may have entered the mansion exactly when the crime started, or left exactly when it was completed.)

Assuming that both culprits are among the N suspects, how many combinations of the two culprits and the crime start time are possible? Here, the order of the two culprits does not matter.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq S_i \leq T_i \leq 10^6
  • 1 \leq D \leq 10^6
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N D
S_1 T_1
S_2 T_2
\vdots
S_N T_N

Output

Output the number of possible combinations of the two culprits and the crime start time.

Sample Input 1

3 2
9 17
10 12
13 20

Sample Output 1

4

In this sample, there are three suspects, and the crime took two units of time.

  • If persons 1 and 2 are the culprits, they were both in the mansion from time 10 to time 12. If the crime start time is time 10, the crime can be committed in two units of time.
  • If persons 1 and 3 are the culprits, they were both in the mansion from time 13 to time 17. If the crime start time is 13, 14, or 15, the crime can be committed in two units of time.
  • If persons 2 and 3 are the culprits, they were never in the mansion at the same time, so this pair cannot have committed the crime.

Thus, the possible combinations of the two culprits and the crime start time are (persons 1, 2, time 10), (persons 1, 3, time 13), (persons 1, 3, time 14), (persons 1, 3, time 15), giving four combinations.

Sample Input 2

3 5
9 17
10 12
13 20

Sample Output 2

0

The suspects are the same as in Sample Input 1, but this time the crime took five units of time.

No matter which two persons are the culprits, the time they were both in the mansion is shorter than the time required for the crime, so the crime is impossible.

Thus, the number of possible combinations of the two culprits and the crime start time is zero. (In other words, our assumption is wrong, and the real culprit has escaped us.)

Sample Input 3

4 1
1 1000000
1 1000000
1 1000000
1 1000000

Sample Output 3

5999994

Beware of overflow for larger cases.