TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

85.3% (29/34)

Submission's AC Ratio

44.4% (59/133)

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 $),彼此間以一個空白隔開,分別代表參賽者的攻擊指數和防禦指數。

子任務(測資) 額外限制 分數
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

Output Format

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

Sample Input

Sample Input #1
9
30 30
60 71
60 65
70 44
80 65
25 25
99 44
100 100
18 19

Sample Input #2
3
99 4
100 3
98 5

Sample Output

Sample Output #1
8

Sample Output #2
0

Hints

Problem Source

2017北市賽(prob 2)

Subtasks

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