問題一覧 > 通常問題

No.2500 Products in a Range

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 59
作問者 : suisen / テスター : emthrm torisasami4 rniya
1 ProblemId : 10101 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-03 00:29:39

問題文

長さ nn の整数列 A=(A1,A2,…,An)A=(A _ 1, A _ 2, \ldots, A _ n) および整数 l,rl, r が与えられます。

AA の 連続とは限らない 部分列 BB であって、次の条件を満たすものを よい部分列 と呼びます。

  • BB の長さを ∣B∣|B| と表す。1≤i<j≤∣B∣1\leq i\lt j\leq |B| を満たす任意の整数 i,ji, j に対して、l≤BiBj≤rl \leq B _ i B _ j\leq r が成り立つ。

特に、長さ 11 の部分列は必ず よい部分列 であることに注意してください。

よい部分列 の長さの最大値を求めてください。

入力

入力は以下の形式で標準入力から与えられます。

n l rn\ l\ r
A1 A2 ⋯AnA _ 1\ A _ 2\ \cdots A _ n
  • 入力は全て整数で与えられる。
  • 1≤n≤50001\leq n\leq 5000
  • −109≤l≤r≤109-10 ^ 9 \leq l\leq r\leq 10 ^ 9
  • −109≤Ai≤109-10 ^ 9 \leq A _ i\leq 10 ^ 9

出力

答えを 11 行に出力し、改行してください。

サンプル

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

この入力は n=5, l=−3, r=6, A=(1,4,−5,3,2)n=5,\ l=-3,\ r=6,\ A=(1,4,-5,3,2) を表します。

例えば B=(1,−5)B=(1,-5) は AA の部分列ですが、B1×B2=−5<−3=lB _ 1 \times B _ 2 = -5 \lt -3 = l より BB は よい部分列 ではありません。

一方 B=(1,3,2)B=(1,3,2) は AA の部分列であり、次の 33 つが成り立つので よい部分列 です。

  • l≤B1×B2=3≤rl\leq B _ 1\times B _ 2 = 3 \leq r
  • l≤B1×B3=2≤rl\leq B _ 1\times B _ 3 = 2 \leq r
  • l≤B2×B3=6≤rl\leq B _ 2\times B _ 3 = 6 \leq r

長さ 44 以上の よい部分列 は存在しないことを証明できるので、この入力に対する答えは 33 となります。

サンプル2
入力
15 48 72
3 -1 4 -1 5 -9 2 -6 5 -3 5 -8 9 -7 9
出力
3

B=(−9,−6,−8)B=(-9,-6,-8) は最長の よい部分列 のうちの一つです。

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