Baltic OI '07 P3 - Sound

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 0.6s
Python 3.0s
Memory limit: 32M
Python 512M
Problem type
Baltic Olympiad in Informatics: 2007 Day 1, Problem 3

In digital recording, sound is described by a sequence of numbers representing the air pressure, measured at a rapid rate with a fixed time interval between successive measurements. Each value in the sequence is called a sample.

An important step in many voice-processing tasks is breaking the recorded sound into chunks of non-silence separated by silence. To avoid accidentally breaking the recording into too few or too many pieces, the silence is often defined as a sequence of m samples where the difference between the lowest and the highest value does not exceed a certain threshold c.

Write a program to detect silence in a given recording of n samples according to the given parameter values m and c.

Input Specification

The first line of the file contains three integers: n (1 \le n \le 1\,000\,000), the number of samples in the recording; m (1 \le m \le 10\,000), the required length of the silence; and c (0 \le c \le 10\,000), the maximal noise level allowed within silence.

The second line of the file contains n integers a_i (0 \le a_i \le 1\,000\,000 for 1 \le i \le n), separated by single spaces: the samples in the recording.

Output Specification

The output should list all values of i such that \max(a[i \dots i + m - 1]) - \min(a[i \dots i + m - 1]) \le c. The values should be listed in increasing order, each on a separate line.

If there is no silence in the input, write NONE on the first and only line of the output.

Sample Input

7 2 0
0 1 1 2 3 2 2

Sample Output

2
6

Comments


  • 6
    billsboard  commented on Dec. 9, 2020, 5:15 p.m. ← edited

    If you're getting MLE on Java, it may be because you're using BufferedReader and calling br.readLine(). 32M is not big enough to hold the second line of input, which can be very long.

    java.util.Scanner is too slow. I used br.read() to take input:

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int readInt() throws IOException{
    int x = 0, c;
    while((c = in.read()) != ' ' && c != '\n')
        x = x * 10 + (c - '0');
    return x;
}