問題一覧 > 通常問題

No.2735 Demarcation

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 20
作問者 : kusirakusira / テスター : 👑 AngrySadEight FplusFplusF hiro1729 みどりむし🦠
お気に入りにしたユーザー ProblemId : 10759 / 自分の提出
問題文最終更新日: 2024-04-19 21:35:12
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 428 (順位表) の他の問題:

Problem Statement

For a sequence $A$ and a positive integer $k$, define $f(k)$ as follows.

  • $f(k) :=$ the number of ways, among the $2^{(|A|-1)}$ ways to split the sequence $A$ into $1$ or more non-empty contiguous subarrays, that satisfy the following condition
For every contiguous subarray, that segment consists of at most $k$ distinct values. (Corrected on 2024/4/19 21:34)

Determine whether a maximum value of $k$ satisfying $f(k) \leqq S$ exists, and if it exists, report that maximum value of $k$.



You are given a sequence $X$ of length $N$ and $Q$ queries. Regarding $(X_l, X_{l+1}, ..., X_r) $ as the sequence $A$, answer the above problem for each query.

Input

$N$
$X_{1}\ X_{2}\ \cdots\ X_{N}$  
$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$
  • All inputs are integers.
  • $1 \leqq N \leqq 10^6$
  • $0 \leqq X_i \leqq N$
  • $1 \leqq Q \leqq 10^4$
  • $1 \leqq l \leqq r \leqq N$
  • $1 \leqq S \leqq 2^{60}$

In the $i$-th query $\text{query}_i$, a tuple of integers $(l, r , S)$ is given in the following format.

$l\ r\ S$


Output

Output the answer to $\text{query}_i$ on line $i$ $(1 \leqq i \leqq Q)$. Specifically, output

  • the value of $k$ if a maximum value of the positive integer $k$ satisfying $f(k) \leqq S$ exists,
  • 0 if no positive integer $k$ satisfying $f(k) \leqq S$ exists,
  • -1 if a positive integer $k$ satisfying $f(k) \leqq S$ exists but no maximum value of it exists.

Sample

Sample 1
Input
7
1 2 3 2 1 1 2
3
1 4 7
2 5 100
3 7 1
Output
2
-1
0

Regarding the $1$st query:
When $k = 2$, the following $6$ ways of splitting satisfy the condition.

  • $[1], [2], [3], [2]$
  • $[1], [2], [3, 2]$
  • $[1], [2, 3], [2]$
  • $[1], [2,3,2]$
  • $[1, 2], [3], [2]$
  • $[1, 2], [3, 2]$
That is, $f(2) = 6$, and this is the largest among the $k$ satisfying $f(k) \leqq 7$.

Sample

Sample 2
Input
3
0 0 0
4
1 3 1
1 3 2
1 3 3
1 3 4
Output
0
0
0
-1

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