E - A Mountain Range with Clear Visibility Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は、東西に一列に並んだ N 個の山を眺めています。各山 i （ 1 \leq i \leq N ）には、山の色を表す値 C_i と、標高 H_i が定められています。

高橋君は、同じ色の山のペアを「対の山」と呼んでいます。対の山同士は景観上の調和があり、写真映えするため、高橋君はそのようなペアに注目しています。

ただし、対の山 i と山 j （ i < j ）の間に、両方の山よりも高い山が存在すると、間の山に遮られて一方から他方が見えなくなってしまいます。具体的には、対の山 i と山 j （ i < j ）について、ある k （ i < k < j ）が存在して H_k > \max(H_i, H_j) を満たすとき、この対は「見通しが悪い」と言います。

高橋君は、対の山のうち見通しが良いペア、すなわち間にどちらの山よりも高い山が存在しないペアの数を数えたいと考えています。

以下の条件をすべて満たす組 (i, j) （ i < j ）の個数を求めてください。

  • C_i = C_j
  • すべての k （ i < k < j ）について H_k \leq \max(H_i, H_j)

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq C_i \leq N
  • 1 \leq H_i \leq 10^9
  • H_i はすべて異なる（すなわち i \neq j ならば H_i \neq H_j）
  • 入力はすべて整数である

入力

N
C_1 H_1
C_2 H_2
:
C_N H_N
  • 1 行目には、山の個数を表す整数 N が与えられる。
  • 2 行目から N + 1 行目では、各山の情報が与えられる。
  • 1 + i 行目には、山 i の色 C_i と標高 H_i が、スペース区切りで与えられる。

出力

同じ色であり、かつ見通しが良いペアの数を 1 行で出力せよ。

入力例 1

5
1 3
2 5
1 4
1 1
2 2

出力例 1

2

入力例 2

4
1 10
2 20
3 30
4 40

出力例 2

0

入力例 3

12
1 8
2 3
1 10
3 1
2 12
1 6
3 9
2 2
1 11
3 5
2 7
3 4

出力例 3

5

入力例 4

30
1 17
2 5
3 28
1 12
4 30
2 9
5 1
3 24
1 20
4 7
5 26
2 14
6 3
1 29
3 11
6 18
4 2
5 22
2 27
7 6
1 15
7 25
3 4
6 21
4 10
5 19
2 8
7 23
6 13
1 16

出力例 4

10

入力例 5

1
1 1

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi is looking at N mountains lined up in a row from east to west. Each mountain i (1 \leq i \leq N) has a color C_i and an elevation H_i.

Takahashi calls a pair of mountains of the same color a "matching pair." Since matching pairs harmonize and look photogenic, Takahashi is interested in them.

However, if there is a mountain between mountain i and mountain j (i < j) that is taller than both of them, it blocks the view, making them invisible to each other. Specifically, for a matching pair i and j (i < j), if there exists some k (i < k < j) such that H_k > \max(H_i, H_j), this pair is said to have a "poor view."

Takahashi wants to count the number of matching pairs with a "clear view," meaning pairs where there is no mountain between them that is strictly taller than both.

Find the number of pairs (i, j) (i < j) that satisfy all of the following conditions:

  • C_i = C_j
  • For all k (i < k < j), H_k \leq \max(H_i, H_j)

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq C_i \leq N
  • 1 \leq H_i \leq 10^9
  • All H_i are distinct (i.e., if i \neq j, then H_i \neq H_j)
  • All input values are integers.

Input

N
C_1 H_1
C_2 H_2
:
C_N H_N
  • The first line contains an integer N, representing the number of mountains.
  • The next N lines (from the 2nd line to the (N + 1)-th line) provide information about each mountain.
  • The (1 + i)-th line contains the color C_i and the elevation H_i of mountain i, separated by a space.

Output

Print the number of pairs of mountains that have the same color and a clear view in a single line.

Sample Input 1

5
1 3
2 5
1 4
1 1
2 2

Sample Output 1

2

Sample Input 2

4
1 10
2 20
3 30
4 40

Sample Output 2

0

Sample Input 3

12
1 8
2 3
1 10
3 1
2 12
1 6
3 9
2 2
1 11
3 5
2 7
3 4

Sample Output 3

5

Sample Input 4

30
1 17
2 5
3 28
1 12
4 30
2 9
5 1
3 24
1 20
4 7
5 26
2 14
6 3
1 29
3 11
6 18
4 2
5 22
2 27
7 6
1 15
7 25
3 4
6 21
4 10
5 19
2 8
7 23
6 13
1 16

Sample Output 4

10

Sample Input 5

1
1 1

Sample Output 5

0