Overview

This problem asks you to count the number of positions where the absolute difference between adjacent temperature data points is at least a threshold value \(K\), given \(N\) temperature data points.

Analysis

The key insight for solving this problem is that the determination of a “sudden change” is self-contained between just two adjacent checkpoints.

To determine whether a sudden change occurred at checkpoint \(i\), we only need the current temperature \(T_i\) and the previous temperature \(T_{i-1}\). Therefore, we can arrive at the correct answer by following these steps:

1. Starting from checkpoint \(2\), calculate the temperature difference with the previous checkpoint.
2. Check whether the absolute value of that difference is at least \(K\).
3. If the condition is satisfied, increment the count by 1.

Looking at the constraints, the number of checkpoints \(N\) is at most \(10^5\). An \(O(N)\) algorithm that checks all checkpoints in a single loop will comfortably fit within the time limit.

Algorithm

1. Read \(N, K\) and the list of temperatures \(T\) from the input.
2. Initialize a variable ans to \(0\) to record the number of sudden changes.
3. For \(i = 1, 2, \dots, N-1\) (using \(0\)-indexed), repeat the following process:
   • Compute \(|T[i] - T[i-1]|\).
   • If that value is at least \(K\), add \(1\) to ans.
4. Output the final value of ans.

*Note: For computing the absolute value, it is convenient to use the abs function available in most programming languages.

Complexity

• Time complexity: \(O(N)\)
  • Since we check each checkpoint exactly once, the computation finishes in time proportional to the input size \(N\).
• Space complexity: \(O(N)\)
  • If we store the input temperatures in a list, we need memory for \(N\) elements.
  • (With some ingenuity, by reading and processing the input one element at a time, this can be reduced to \(O(1)\).)

Implementation Notes

• Index range: Since checkpoint \(1\) has no “previous checkpoint,” the loop must start from the second element (index \(1\)).

• Handling large input: In Python, repeatedly calling input() can lead to long execution times. For \(N = 10^5\) or so, you can process input efficiently by reading everything at once using sys.stdin.read().split() or similar methods.

• Absolute value check: The condition \(|T_i - T_{i-1}| \ge K\) can be written in code as abs(T[i] - T[i-1]) >= K.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: チェックポイントの数, K: 基準値
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 気温のリスト T (T_1, T_2, ..., T_N)
    T = list(map(int, input_data[2:]))
    
    ans = 0
    # チェックポイント 2 から N まで順に確認する
    for i in range(1, N):
        # 直前のチェックポイントとの気温差の絶対値が K 以上か判定
        if abs(T[i] - T[i-1]) >= K:
            ans += 1
            
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.