皇家機器人 AI 格鬥大賽即將開打,根據比賽規則,所有參賽者會被隨機排成一列,然後從左右最鄰近的兩個對手開始對戰。若能打敗左(或右)邊的第一個對手,才能繼續跟左(或右)邊的第二個對手對戰。被分配到最左(或右)邊的參賽者運氣不好,他們一開始就只能往右(或左)邊對戰。
瑞奇是格鬥大賽的主播,他很喜歡預測比賽結果。他會搜集參賽者的資料,評估出參賽者的攻擊指數和防禦指數。他認為只要兩個指數有一個高於對手,而且另一個不低於對手(攻擊指數和攻擊指數相比,防禦指數和防禦指數相比),就能贏得該場戰鬥。
以上面的數據為例,有 9 位參賽者。瑞奇預測 5 號參賽者將可贏得三場勝利:戰勝 4號(5 號的兩個指數皆較高)、3(5 號的攻擊指數較高且防禦指數相同)以及 6(5 號的兩個指數皆較高)的對手。5 號無法戰勝 2 號對手,因為 2 號的防禦指數比 5 號的防禦指數高;同理,5 號無法戰勝 7 號的對手,因為 7 號的攻擊指數比 5 號的攻擊指數高。
根據瑞奇的預測方法,請寫一個程式輸出勝場最多的參賽者會贏幾場。以上面的例子來說,他預測的勝場數為:
因此勝場數最多為 8 場。
第一列為一個正整數 N,代表參賽者數。
接下來的 N 列為參賽者資料,第一列為最左邊參賽者的資料,接著依序到最右邊參賽者的資料。每一列有兩個正整數 $a_i$ 和 $d_i$ ($0 \leq a_i , d_i \leq 2 \times 10 ^ {9} , 1 \leq i \leq N $),彼此間以一個空白隔開,分別代表參賽者的攻擊指數和防禦指數。
輸出一正整數,為勝場最多的參賽者會贏幾場。
2017北市賽(prob 2)
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 |