No.686 Uncertain LIS

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 9
作問者 : PulmnPulmn / テスター : square1001square1001

2 ProblemId : 1887 / 出題時の順位表

問題文

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

条件:数列 $A$ の長さは $N$ で、$1\le i\le N$ を満たす全ての $i$ について $A_i$ は整数であり $L_i\le A_i\le R_i$ が成り立つ。

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

入力

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

$1\le N\le 10^5$
$1\le L_i\le R_i\le 10^5$ $(1\le i\le 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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。