Baltic OI '07 P3 - Sound - DMOJ: Modern Online Judge

Baltic OI '07 P3 - Sound

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$ $m$ samples where the difference between the lowest and the highest value does not exceed a certain threshold $c$ $c$ .

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

Input Specification

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

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

Output Specification

The output should list all values of $i$ $i$ such that $\max(a[i \dots i + m - 1]) - \min(a[i \dots i + m - 1]) \le c$ $max (a [i \dots i + m - 1]) - min (a [i \dots i + m - 1]) \leq 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

Copy

7 2 0
0 1 1 2 3 2 2

Sample Output

Copy

2
6

Comments

8
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:

Copy
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; }