/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 333 点
問題文
高橋君は工場の品質管理システムを開発しています。このシステムでは、製造ラインに設置されたセンサーから取得したデータを監視し、異常な期間を検出する必要があります。
センサーは N 回の計測を行い、第 1 回目から第 N 回目まで順番にデータが記録されています。第 i 回目（1 \leq i \leq N）の計測で得られた値は「品質指標」と呼ばれる整数値 A_i です。品質指標は正の値、0、または負の値をとり得ます。
品質管理の基準として、連続するちょうど K 回分の計測における品質指標の合計が 0 以下になる場合、その区間を「異常期間」と判定します。より正確には、各開始位置 j（1 \leq j \leq N - K + 1）に対して、
A_j + A_{j+1} + \cdots + A_{j+K-1} \leq 0
が成り立つとき、開始位置 j の区間（第 j 回目から第 j+K-1 回目まで）は異常期間です。
異常期間と判定される区間の個数、すなわち上の条件を満たす開始位置 j の個数を求めてください。異なる開始位置に対応する区間は、たとえ互いに重なり合っていてもそれぞれ別々に数えます。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- -10^9 \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 が、スペース区切りで与えられる。
出力
異常期間と判定される区間の個数を 1 行で出力してください。
入力例 1
5 3 2 -1 -3 4 1
出力例 1
2
入力例 2
8 4 1 -2 3 -4 2 -1 -3 5
出力例 2
4
入力例 3
15 5 100 -50 -30 -25 10 -200 150 80 -100 -60 20 -10 5 -15 30
出力例 3
7
Score : 333 pts
Problem Statement
Takahashi is developing a quality control system for a factory. This system needs to monitor data collected from sensors installed on the manufacturing line and detect abnormal periods.
The sensor performs N measurements, and data is recorded in order from the 1-st to the N-th measurement. The value obtained at the i-th measurement (1 \leq i \leq N) is an integer A_i called the "quality index." The quality index can be positive, 0, or negative.
As a quality control criterion, if the sum of quality indices over a window of exactly K consecutive measurements is 0 or less, that interval is classified as an "abnormal period." More precisely, for each starting position j (1 \leq j \leq N - K + 1), if
$A_j + A_{j+1} + \cdots + A_{j+K-1} \leq 0$
holds, then the interval starting at position j (from the j-th to the (j+K-1)-th measurement) is an abnormal period.
Find the number of intervals classified as abnormal periods, that is, the number of starting positions j satisfying the above condition. Intervals corresponding to different starting positions are counted separately, even if they overlap with each other.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- -10^9 \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 measurements and an integer K representing the length of the interval used for anomaly detection, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the quality index of each measurement, separated by spaces.
Output
Print the number of intervals classified as abnormal periods in a single line.
Sample Input 1
5 3 2 -1 -3 4 1
Sample Output 1
2
Sample Input 2
8 4 1 -2 3 -4 2 -1 -3 5
Sample Output 2
4
Sample Input 3
15 5 100 -50 -30 -25 10 -200 150 80 -100 -60 20 -10 5 -15 30
Sample Output 3
7