TopCoder

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

User's AC Ratio

91.9% (91/99)

Submission's AC Ratio

38.4% (144/375)

Tags

Description

皇家機器人 AI 格鬥大賽即將開打,根據比賽規則,所有參賽者會被隨機排成一列,然後從左右最鄰近的兩個對手開始對戰。若能打敗左(或右)邊的第一個對手,才能繼續跟左(或右)邊的第二個對手對戰。被分配到最左(或右)邊的參賽者運氣不好,他們一開始就只能往右(或左)邊對戰。
瑞奇是格鬥大賽的主播,他很喜歡預測比賽結果。他會搜集參賽者的資料,評估出參賽者的攻擊指數和防禦指數。他認為只要兩個指數有一個高於對手,而且另一個不低於對手(攻擊指數和攻擊指數相比,防禦指數和防禦指數相比),就能贏得該場戰鬥。

以上面的數據為例,有 9 位參賽者。瑞奇預測 5 號參賽者將可贏得三場勝利:戰勝 4號(5 號的兩個指數皆較高)、3(5 號的攻擊指數較高且防禦指數相同)以及 6(5 號的兩個指數皆較高)的對手。5 號無法戰勝 2 號對手,因為 2 號的防禦指數比 5 號的防禦指數高;同理,5 號無法戰勝 7 號的對手,因為 7 號的攻擊指數比 5 號的攻擊指數高。
根據瑞奇的預測方法,請寫一個程式輸出勝場最多的參賽者會贏幾場。以上面的例子來說,他預測的勝場數為:

因此勝場數最多為 8 場。

Input Format

第一列為一個正整數 N,代表參賽者數。
接下來的 N 列為參賽者資料,第一列為最左邊參賽者的資料,接著依序到最右邊參賽者的資料。每一列有兩個正整數 $a_i$ 和 $d_i$ ($0 \leq a_i , d_i \leq 2 \times 10 ^ {9} , 1 \leq i \leq N $),彼此間以一個空白隔開,分別代表參賽者的攻擊指數和防禦指數。

Output Format

輸出一正整數,為勝場最多的參賽者會贏幾場。

Sample Input 1

9
30 30
60 71
60 65
70 44
80 65
25 25
99 44
100 100
18 19

Sample Output 1

8

Sample Input 2

3
99 4
100 3
98 5

Sample Output 2

0

Hints

Problem Source

2017北市賽(prob 2)

Subtasks

No. Testdata Range Constraints Score
1 0~10 $N \leq 100$ 27
2 11~21 $N \leq 1000000, a_{i} < a_{i+1}, d_{i} \in \{ 0,1,2,3 \} $ 27
3 22~43 $N \leq 1500000$ 46

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 262144 1
1 1000 524288 262144 1
2 1000 524288 262144 1
3 1000 524288 262144 1
4 1000 524288 262144 1
5 1000 524288 262144 1
6 1000 524288 262144 1
7 1000 524288 262144 1
8 1000 524288 262144 1
9 1000 524288 262144 1
10 1000 524288 262144 1
11 1000 524288 262144 2
12 1000 524288 262144 2
13 1000 524288 262144 2
14 1000 524288 262144 2
15 1000 524288 262144 2
16 1000 524288 262144 2
17 1000 524288 262144 2
18 1000 524288 262144 2
19 1000 524288 262144 2
20 1000 524288 262144 2
21 1000 524288 262144 2
22 1000 524288 262144 3
23 1000 524288 262144 3
24 1000 524288 262144 3
25 1000 524288 262144 3
26 1000 524288 262144 3
27 1000 524288 262144 3
28 1000 524288 262144 3
29 1000 524288 262144 3
30 1000 524288 262144 3
31 1000 524288 262144 3
32 1000 524288 262144 3
33 1000 524288 262144 3
34 1000 524288 262144 3
35 1000 524288 262144 3
36 1000 524288 262144 3
37 1000 524288 262144 3
38 1000 524288 262144 3
39 1000 524288 262144 3
40 1000 524288 262144 3
41 1000 524288 262144 3
42 1000 524288 262144 3
43 1000 524288 262144 3