TopCoder

Thumb fhvirus
FHVirus
$\huge{WHP}$

User's AC Ratio

93.8% (30/32)

Submission's AC Ratio

31.6% (42/133)

Description

  你與滷肉在大不列顛帝國最引以為傲的高速公路上奔馳著。

  好友滷肉發現高速公路上每輛車子都以等速度向右前進。

  你也注意到一個有趣的現象:就算都是等速度,還是有時會有車子超過其他車子!

  現在你知道每輛車子的位置以及速度,你能知道之後會有多少超車事件嗎?

Input Format

本題有多筆測試資料,請以 EOF 作為結束
每組的:
 第一行有一個數字 $n$,代表車子的數量($1 \leq n \leq 1000000$)
 第二行到第 $n+1$ 行,每行有兩個數字 $X_i$ 及 $V_i$ 以空白隔開,代表第 $i$ 輛車子的位置以及速度($0 \leq X,V \leq1000000$)

Output Format

對於每筆資料輸出一行 $p$,代表之後會發現 $p$ 件超車事件

Sample Input

2
0 3
1 2

Sample Output

1

Hints

※2008/07/17 補上測資範圍 by hallogameboy。 感謝 newmoon。
※2008/07/17 修改測資範圍 by hallogameboy。 感謝 Robin。

Problem Source

原TIOJ1365 / 快樂暑假營第二次練習比賽。Problem Setter:hallogameboy
2021/03/06 Update: Added $\LaTeX$ by FHVirus

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1