No.2735 Demarcation
レベル :
/ AI推定難易度 : 1900
/ 実行時間制限 : 1ケース 1.500秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 :
kusirakusira
/ テスター :
👑
AngrySadEight
FplusFplusF
hiro1729
みどりむし🦠
タグ : / 解いたユーザー数 20
作問者 :
kusirakusira
/ テスター :
👑
FplusFplusF
みどりむし🦠
問題文最終更新日: 2024-04-19 21:35:12
English (AI translation)
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,
0if no positive integer $k$ satisfying $f(k) \leqq S$ exists,-1if 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]$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。