BOI7SOU - Sound
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
The first line of the file contains three integers: n (1 ≤ n ≤ 1,000,000), the number of samples in the recording; m (1 ≤ m ≤ 10,000), the required length of the silence; and c (0 ≤ c ≤ 10,000), the maximal noise level allowed within silence. The second line of the file contains n integers ai (0 ≤ ai ≤ 1,000,000 for 1 ≤ i ≤ n), separated by single spaces: the samples in the recording.
Output
The file should list all values of i such that max(a[i . . . i + m − 1]) − min(a[i . . . i + m − 1]) ≤ c. The values should be listed in increasing order, each on a separate line. If there is no silence in the input file, write NONE on the first and only line of the output file.
Example
Input:
7 2 0
0 1 1 2 3 2 2
Output: 2
6
hide comments
siddharth_0196:
2017-05-13 15:17:41
O(nlogn) gives TLE! |
|
mrinal_aich:
2016-09-21 13:13:19
You may use hash-map and queue of STL in C++. |
|
Adamos Ttofari:
2015-07-12 10:55:09
I can't get it... My solution passes the official test data and I get a WA here :( |
|
eightnoteight:
2015-06-15 17:43:38
nice problem; did it using simple stl map |
|
maniAC:
2014-08-04 23:18:14
O(nlogn) Sparse table got TLE. O(n) Deque got AC. |
|
Master Wad7a:
2013-05-06 10:18:48
AC in O(n log n) , but used fast input and a BIT (which in these cases is much faster than segment tree) :THATS A HINT |
|
Nikhil Garg:
2010-12-31 17:05:52
Time limit is too strict. My O(N) solution times out. Too much IO.
|
|
Dominik Kempa:
2010-11-04 22:44:47
@problem setter: did you add your own tests? My solution passes official testdata. WA here...
|
Added by: | Race with time |
Date: | 2010-11-04 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Baltic Olympiad 2007 |