問題一覧 > 通常問題

No.1804 Intersection of LIS

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 43
作問者 : NatsubiSoganNatsubiSogan / テスター : nok0nok0 penguinmanpenguinman
2 ProblemId : 7029 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-17 20:14:24

問題文

$(1,2,\dots,N)$ を並び替えた数列 $P=(P_1,P_2,\dots,P_N)$ が与えられます。 $P$ の LIS(最長増加部分列)として考えられるものはいくつかありますが、その すべて に含まれる要素を列挙してください。

入力

$N$
$P_1$ $P_2$ $\ldots$ $P_N$
  • 入力はすべて整数
  • $1 \leq N \leq 3 \times 10^5$
  • $P$ は $(1,2,\dots,N)$ を並び替えた数列

出力

まず、$1$ 行目に、$P$ のすべての LIS に含まれる要素の個数を出力してください。

その後、$2$ 行目に、$P$ のすべての LIS に含まれる要素を、添え字の昇順に 空白区切りで出力してください。なお、要素数が $0$ の場合は、$2$ 行目に空行を出力してください。

最後に改行してください。

サンプル

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

LIS として考えられるものは、$(A_1,A_2,A_5)=(1,4,5), \ (A_1,A_3,A_5)=(1,3,5), \ (A_1,A_4,A_5)=(1,2,5)$ の $3$ つです。

これらのいずれにも含まれるのは $A_1 = 1, A_5 = 5$ なので、これらを出力します。

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

LIS は $(A_1,A_2)=(2,3)$ のみです。

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

すべての LIS に含まれる要素の数が $0$ である場合もあります。このような場合において、$2$ 行目は空行として出力することを忘れないで下さい。

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