問題一覧 > 通常問題

No.686 Uncertain LIS

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

問題文

次の条件を満たす数列 $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

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