問題一覧 > 通常問題

No.2735 Demarcation

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : kusirakusirakusirakusira / テスター : 👑 AngrySadEightAngrySadEight FplusFplusFFplusFplusF hiro1729hiro1729 🦠みどりむし🦠みどりむし
2 ProblemId : 10759 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-19 21:35:12

問題文

数列 AA、正整数 kk に対し、f(k)f(k) を以下のように定義します。

  • f(k):=f(k) := 数列 AA11 つ以上の空ではない連続部分列に分割する 2(A1)2^{(|A|-1)} 通りの方法のうち、次の条件を満たすものの個数
すべての連続部分列について、その区間が kk 種類以下のからなる。(2024/4/19 21:34修正)

f(k)Sf(k) \leqq S を満たす kk の最大値か存在するか判定し、存在するならそのときの kk の最大値を答えてください。



長さ NN の数列 XX とクエリが QQ 個与えられます。(Xl,Xl+1,...,Xr)(X_l, X_{l+1}, ..., X_r) を数列 AA と見なしたとき、以上の問題にそれぞれ答えてください。

入力

NN
X1 X2  XNX_{1}\ X_{2}\ \cdots\ X_{N}  
QQ
query1\text{query}_1
query2\text{query}_2
\vdots
queryQ\text{query}_Q
  • 入力はすべて整数である。
  • 1N1061 \leqq N \leqq 10^6
  • 0XiN0 \leqq X_i \leqq N
  • 1Q1041 \leqq Q \leqq 10^4
  • 1lrN1 \leqq l \leqq r \leqq N
  • 1S2601 \leqq S \leqq 2^{60}

ii 番目のクエリ queryi\text{query}_i では 整数組 (l,r,S)(l, r , S) が以下の形式で与えられます。

l r Sl\ r\ S


出力

queryi\text{query}_i の答えを ii 行目 (1iQ)(1 \leqq i \leqq Q)に出力してください。 具体的には

  • f(k)Sf(k) \leqq S を満たす正整数 kk の最大値が存在する場合は、そのときの kk の値
  • f(k)Sf(k) \leqq S を満たす正整数 kk が存在しない場合は、0
  • f(k)Sf(k) \leqq S を満たす正整数 kk は存在するが、その最大値が存在しない場合、-1
を出力してください。

サンプル

サンプル1
入力
7
1 2 3 2 1 1 2
3
1 4 7
2 5 100
3 7 1
出力
2
-1
0

11 つ目のクエリについて:
k=2k = 2 のとき、条件を満たす分割方法は以下の 66 つです。

  • [1],[2],[3],[2][1], [2], [3], [2]
  • [1],[2],[3,2][1], [2], [3, 2]
  • [1],[2,3],[2][1], [2, 3], [2]
  • [1],[2,3,2][1], [2,3,2]
  • [1,2],[3],[2][1, 2], [3], [2]
  • [1,2],[3,2][1, 2], [3, 2]
すなわち、f(2)=6f(2) = 6 であり f(k)7f(k) \leqq 7 を満たす kk の中で最大です。

サンプル

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

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