E - Choosing Flowerbed Intervals Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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、すなわち花が 1 本だけの場合も含みます）。

展示コーナーの見栄えをよくするため、高橋君は以下の 2 つの条件を同時に満たす 区間を選びたいと考えています。

条件 1（品種の多様さに関する条件）：

区間 [l, r] に含まれる花の品種番号 A_l, A_{l+1}, \ldots, A_r の中に含まれる 異なる値の個数 を D とします。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

を満たす必要があります。

上記の 2 条件を同時に満たす区間 [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
  • 1 行目には、花の本数を表す整数 N、条件 1 における積の上限を表す整数 K、条件 2 における高さの差の上限を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各花の品種番号を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、各花の高さを表す整数 B_1, B_2, \ldots, B_N が、スペース区切りで与えられる。

出力

条件 1 と条件 2 を同時に満たす区間 [l, r] (1 \le l \le r \le N) の個数を 1 行で出力せよ。

入力例 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

Score : 433 pts

Problem Statement

Takahashi is in charge of managing a flowerbed. The flowerbed has N flowers planted in a row, numbered 1, 2, \ldots, N from left to right.

Each flower i (1 \le i \le N) has a recorded "variety number" A_i and "height" B_i. Takahashi wants to select a contiguous interval of flowers to create an exhibition section. An interval [l, r] (1 \le l \le r \le N) chosen as the exhibition section is the contiguous sequence of flowers from flower l to flower r (including the case where l = r, i.e., only a single flower).

To make the exhibition section look attractive, Takahashi wants to choose an interval that satisfies both of the following 2 conditions simultaneously.

Condition 1 (Variety diversity condition):

Let D be the number of distinct values among the variety numbers A_l, A_{l+1}, \ldots, A_r of flowers in the interval [l, r]. The product of D and the length of the interval (r - l + 1) must be at most K. That is,

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

must be satisfied.

Condition 2 (Height balance condition):

The difference between the maximum and minimum heights of flowers in the interval [l, r] must be at most M. That is,

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

must be satisfied.

Find the number of intervals [l, r] (1 \le l \le r \le N) that satisfy both conditions above simultaneously.

Constraints

  • 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
  • All inputs are integers.

Input

N K M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
  • The first line contains the integer N representing the number of flowers, the integer K representing the upper bound of the product in Condition 1, and the integer M representing the upper bound of the height difference in Condition 2, separated by spaces.
  • The second line contains the integers A_1, A_2, \ldots, A_N representing the variety number of each flower, separated by spaces.
  • The third line contains the integers B_1, B_2, \ldots, B_N representing the height of each flower, separated by spaces.

Output

Output in one line the number of intervals [l, r] (1 \le l \le r \le N) that satisfy both Condition 1 and Condition 2 simultaneously.

Sample Input 1

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

Sample Output 1

10

Sample Input 2

4 2 0
1 1 2 2
5 5 6 6

Sample Output 2

6

Sample Input 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

Sample Output 3

48

Sample Input 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

Sample Output 4

216

Sample Input 5

1 1 0
1
1000000000

Sample Output 5

1