/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は登山が趣味で、ある山脈の縦走ルートを計画しています。この山脈には N 個の地点が 1 から N の順に一列に並んでおり、各地点 i（1 \leq i \leq N）の標高は A_i メートルです。
高橋君は、1 \leq l \leq r \leq N を満たす整数の組 (l, r) を 1 つ選び、地点 l から地点 r まで番号の昇順に各地点を順番に通過するルートを歩きます。このルートに含まれる地点の数は r - l + 1 です。
このルートの総高低差を、ルート上で隣接する地点間の標高差の絶対値の合計、すなわち
\sum_{i=l}^{r-1} |A_{i+1} - A_i|
と定義します。なお、l = r の場合はこの和は空和となるため、総高低差は 0 です。
高橋君はトレーニングのために、総高低差が K 以上となるルートを歩きたいと考えています。しかし、時間に余裕がないため、条件を満たすルートの中で含まれる地点の数が最も少ないものを選びたいです。
総高低差が K 以上となるルートが存在するならば、そのようなルートに含まれる地点の数の最小値を求めてください。存在しない場合は -1 を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{18}
- 0 \leq A_i \leq 10^9
- 入力はすべて整数である
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、地点の数を表す整数 N と、総高低差の下限を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各地点の標高を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
総高低差が K 以上となるルートが存在する場合、そのようなルートに含まれる地点の数の最小値を 1 行で出力せよ。存在しない場合は -1 を出力せよ。
入力例 1
5 5 1 4 2 5 3
出力例 1
3
入力例 2
3 100 1 2 3
出力例 2
-1
入力例 3
10 15 0 10 3 8 1 9 2 7 4 6
出力例 3
3
入力例 4
20 500 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100
出力例 4
6
入力例 5
1 1 1000000000
出力例 5
-1
Score : 366 pts
Problem Statement
Takahashi enjoys mountain climbing and is planning a traverse route through a mountain range. The mountain range has N points arranged in a line, numbered from 1 to N, and the elevation of each point i (1 \leq i \leq N) is A_i meters.
Takahashi chooses a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N, and walks a route that passes through each point in order from point l to point r in ascending order of their numbers. The number of points included in this route is r - l + 1.
The total elevation change of this route is defined as the sum of the absolute differences in elevation between adjacent points along the route, namely:
\sum_{i=l}^{r-1} |A_{i+1} - A_i|
Note that when l = r, this sum is an empty sum, so the total elevation change is 0.
Takahashi wants to walk a route with a total elevation change of at least K for training purposes. However, since he is short on time, he wants to choose a route that satisfies the condition while containing the fewest number of points.
If a route with a total elevation change of at least K exists, find the minimum number of points included in such a route. If no such route exists, output -1.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{18}
- 0 \leq A_i \leq 10^9
- All input values are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of points and an integer K representing the lower bound on the total elevation change, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the elevation of each point, separated by spaces.
Output
If a route with a total elevation change of at least K exists, output the minimum number of points included in such a route on a single line. If no such route exists, output -1.
Sample Input 1
5 5 1 4 2 5 3
Sample Output 1
3
Sample Input 2
3 100 1 2 3
Sample Output 2
-1
Sample Input 3
10 15 0 10 3 8 1 9 2 7 4 6
Sample Output 3
3
Sample Input 4
20 500 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100
Sample Output 4
6
Sample Input 5
1 1 1000000000
Sample Output 5
-1