/ 
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
(1,\ldots,N) を並び替えて得られる長さ N の順列 P=(P_1,\ldots,P_N)、及び整数 K が与えられます。
以下の条件を全て満たす整数組 (L,R) の個数を求めてください。
-
1 \leq L \leq R \leq N
-
\mathrm{max}(P_L,\ldots,P_R) - \mathrm{min}(P_L,\ldots,P_R) \leq R - L + K
制約
- 1 \leq N \leq 1.4\times 10^5
- P は (1,\ldots,N) を並び替えて得られる順列
- 0 \leq K \leq 3
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K P_1 P_2 \ldots P_N
出力
答えを出力せよ。
入力例 1
4 1 1 4 2 3
出力例 1
9
条件を満たす組 (L,R) は以下の 9 個です。
- (1,1)
- (1,3)
- (1,4)
- (2,2)
- (2,3)
- (2,4)
- (3,3)
- (3,4)
- (4,4)
(L,R) = (1,2) は \mathrm{max}(A_1,A_2) -\mathrm{min}(A_1,A_2) = 4-1 = 3 、R-L+K=2-1+1 = 2 となるので、条件を満たしません。
入力例 2
2 0 2 1
出力例 2
3
入力例 3
10 3 3 7 10 1 9 5 4 8 6 2
出力例 3
37
Score : 600 points
Problem Statement
You are given a permutation P=(P_1,\ldots,P_N) of (1,\ldots,N), and an integer K.
Find the number of pairs of integers (L, R) that satisfy all of the following conditions:
-
1 \leq L \leq R \leq N
-
\mathrm{max}(P_L,\ldots,P_R) - \mathrm{min}(P_L,\ldots,P_R) \leq R - L + K
Constraints
- 1 \leq N \leq 1.4\times 10^5
- P is a permutation of (1,\ldots,N).
- 0 \leq K \leq 3
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K P_1 P_2 \ldots P_N
Output
Print the answer.
Sample Input 1
4 1 1 4 2 3
Sample Output 1
9
The following nine pairs (L, R) satisfy the conditions.
- (1,1)
- (1,3)
- (1,4)
- (2,2)
- (2,3)
- (2,4)
- (3,3)
- (3,4)
- (4,4)
For (L,R) = (1,2), we have \mathrm{max}(A_1,A_2) -\mathrm{min}(A_1,A_2) = 4-1 = 3 and R-L+K=2-1+1 = 2, not satisfying the condition.
Sample Input 2
2 0 2 1
Sample Output 2
3
Sample Input 3
10 3 3 7 10 1 9 5 4 8 6 2
Sample Output 3
37