1365 . 超車問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

88.4% (38/43)

Submission's AC Ratio

32.1% (52/162)

Tags

CKsum 2008-CKsum-2nd

Description

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

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

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

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

Input Format

本題有多筆測試資料，請以 EOF 作為結束
每組的：
　第一行有一個數字 n，代表車子的數量（1≤n≤1000000）
　第二行到第 n+1 行，每行有兩個數字 Xi 及 Vi 以空白隔開，代表第 i 輛車子的位置以及速度（0≤X,V≤1000000）

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