← 返回题目列表

AtCoder · awc0101_e

E. 选择花坛间隔

中文机器翻译题面 查看原题

分数: 433 分

问题陈述

高桥负责管理花坛。花坛有 N 花连续种植,已编号 1, 2, \ldots, N 从左到右。

每朵花 i (1 \le i \le N) 已记录“品种号” A_i 和“高度” B_i。高桥想要选择一个连续的花朵间隔来创建一个展览区。一个区间 [l, r] (1 \le l \le r \le N) 选择作为展览部分的是花中连续的花朵序列 l 要花 r (包括以下情况 l = r,即只有一朵花)。

为了使展览部分看起来有吸引力,高桥想选择一个间隔 同时满足以下2个条件.

条件1(品种多样性条件):

让 D 是 不同值的数量 品种编号之中 A_l, A_{l+1}, \ldots, A_r 间隔中的花朵 [l, r]。的产品 D 和间隔的长度 (r - l + 1) 最多必须是 K。也就是说, 必须满足

D \times (r - l + 1) \le K

。

条件2(高度平衡条件):

区间内花朵的最大高度与最小高度之差 [l, r] 最多必须是 M。也就是说, 必须满足

\max_{l \le i \le r} B_i - \min_{l \le i \le r} B_i \le M

。

查找间隔数 [l, r] (1 \le l \le r \le N) 同时满足上述两个条件。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{18}
  • 0 \leq M \leq 10^9
  • 1 \leq A_i \leq N
  • 1 \leq B_i \leq 10^9
  • 所有输入均为整数。

输入

N K M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
  • 第一行包含整数 N 代表鲜花数量,整数 K 表示条件 1 中乘积的上限,整数 M 表示条件 2 中高度差的上限,以空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每朵花的品种号,以空格分隔。
  • 第三行包含整数 B_1, B_2, \ldots, B_N 代表每朵花的高度,以空格分隔。

输出

在一行中输出间隔数 [l, r] (1 \le l \le r \le N) 同时满足条件1和条件2。


示例输入 1

5 6 3
1 2 1 3 2
4 5 7 6 8

示例输出 1

10

示例输入 2

4 2 0
1 1 2 2
5 5 6 6

示例输出 2

6

示例输入 3

12 20 10
1 2 3 2 1 4 4 5 3 2 6 1
10 12 15 18 14 20 21 19 13 11 16 17

示例输出 3

48

示例输入 4

40 100 50
1 2 3 4 5 1 2 6 7 8 3 4 9 10 1 11 12 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12
100 120 130 160 170 150 140 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430 440 450 460 470 480 490 500

示例输出 4

216

示例输入 5

1 1 0
1
1000000000

示例输出 5

1