P4392 [BalticOI 2007] Sound Silence Problem

In digital audio recording, sound is represented by a sequence of numbers describing air pressure, with each value called a sample, and adjacent samples separated by equal time intervals. Many audio processing tasks need to split the recorded sound into non-silent segments separated by silence. To avoid producing too many or too few non-silent segments, silence is defined as follows: a sequence of $m$ samples in which the difference between the maximum and the minimum sample values does not exceed a given threshold $c$. Write a program to detect silence within $n$ samples.

The first line contains three integers $n, m, c$ ($1 \le n \le 10^6$, $1 \le m \le 10^4$, $0 \le c \le 10^4$), denoting the total number of samples, the length of a silence segment, and the maximum allowed noise level within a silence segment. The second line contains $n$ integers $a_i$ ($0 \le a_i \le 10^6$), the value of each sample, separated by spaces.

List all starting positions $i$ of silence segments (i.e., those $i$ such that $\max\{a_i, a_{i+1}, \ldots, a_{i+m-1}\} - \min\{a_i, a_{i+1}, \ldots, a_{i+m-1}\} \le c$). Output one starting position per line, in order of appearance. If there is no silence, output `NONE`.

Translated by ChatGPT 5