P15278 [MCO 2025] Subsequence

给定一个数组 $a$ 和一个整数 $X$，你的任务是找出数组 $a$ 中最长的 **有效** 子序列。一个子序列是 **有效** 的，当且仅当该子序列中任意相邻元素的乘积都不超过 $X$。也就是说，设 $b$ 是 $a$ 的一个长度为 $m$ 的子序列，则 $b$ 是 **有效** 的，当且仅当对于任意 $i$ （$1 \leq i \leq m-1$），都有 $b_i \cdot b_{i+1} \leq X$。 注意：数组 $b$ 是另一个数组 $a$ 的子序列，当且仅当 $b$ 可以通过从数组 $a$ 中移除若干元素（也可以不移除）且不改变剩余元素的顺序得到。例如，数组 $[1,3]$ 是 $[1,2,3]$ 的一个子序列，而数组 $[2,1]$ 和数组 $[1,4]$ **不是** $[1,2,3]$ 的子序列。

第一行包含两个以空格分隔的整数 $n$ （$1 \leq n \leq 10^5$）和 $X$ （$0 \leq |X| \leq 10^{18}$）—— $n$ 是数组 $a$ 的长度，$X$ 是给定的整数。 第二行包含 $n$ 个以空格分隔的整数 $a_1, a_2, \dots, a_n$ （$1 \leq |a_i| \leq 10^9$）。

输出一行一个整数，表示最长 **有效** 子序列的长度。

#### 注释 **示例 1** 只有一个元素的子序列总是有效的，因为不存在相邻元素。因此，最长有效子序列的长度为 $1$。 **示例 2** 本例中有一个有效子序列 $[3,2,5,1]$。其相邻元素的乘积均不超过 $10$，如下所示： - $3 \times 2 = 6 \,(\leq 10)$ - $2 \times 5 = 10 \,(\leq 10)$ - $5 \times 1 = 5 \,(\leq 5)$ 子序列 $[\underline{3,4},2,5,1]$（即原数组 $a$）是 **无效** 的，因为第一个和第二个元素的乘积为 $12$，超过了 $10$。 因此，最长有效子序列的长度为 $4$。 **示例 3** 本例中最长有效子序列是 $[6,-2,-2,5]$。 子序列 $[6,-2,\underline{-2, -6}, 5]$（即原数组 $a$）是 **无效** 的，因为第三个和第四个元素的乘积为 $-2 \times -6 = 12$，超过了 $10$。 #### 计分 **子任务 1** （$5$ 分）： $X = 10^{18}$ **子任务 2** （$15$ 分）： $n \leq 20$ **子任务 3** （$20$ 分）： $n \leq 10^3$ **子任务 4** （$10$ 分）： $X \geq 0$，且对于所有 $1 \leq i \leq n$，有 $1 \leq a_i \leq 200$ **子任务 5** （$20$ 分）： $X \geq 0$，且对于所有 $1 \leq i \leq n$，有 $1 \leq a_i \leq 10^5$ **子任务 6** （$10$ 分）： $X \geq 0$，且对于所有 $1 \leq i \leq n$，有 $a_i \geq 1$ **子任务 7** （$20$ 分）： 无额外限制 翻译由 DeepSeek 完成