問題一覧 > 通常問題

No.686 Uncertain LIS

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : Pulmn / テスター : square1001
5 ProblemId : 1887 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-05-18 18:53:13

問題文

次の条件を満たす数列 A の最長増加部分列の長さの中で最大の長さを求めてください。なお、数列の番号は 1-indexed です。

条件：数列 A の長さは N で、1≤i≤N を満たす全ての i について Ai は整数であり Li≤Ai≤Ri が成り立つ。

※ A の最長増加部分列とは、A の狭義単調増加な部分列のなかで最も長い部分列を意味します。

入力

N
L1 R1
L2 R2
⋮
LN RN

1≤N≤105
1≤Li≤Ri≤105 (1≤i≤N)

出力

考えられる最長増加部分列の長さの最大値を出力してください。最後に改行してください。

サンプル

サンプル1
入力
5
3 5
1 3
2 7
1 2
2 3
出力
3

例えば、A={3,1,2,2,3} とすると、最長増加部分列は {1,2,3} になり、最長増加部分列の長さは 3 になります。

サンプル2
入力
1
1 100000
出力
1

サンプル3
入力
5
1 1
2 2
3 3
4 4
5 5
出力
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。