1365 . 超車問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

88.1% (37/42)

Submission's AC Ratio

31.7% (51/161)

Tags

CKsum 2008-CKsum-2nd

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 1

2
0 3
1 2

Sample Output 1

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 (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
Submit
Back to Top