Задача №111578. Звук тишины
Цифровая звукозапись представляет собой набор чисел, задающих давление воздуха. Замеры уровня давления происходят с большой частотой через равные промежутки времени. Каждое значение в этой последовательности называется сэмплом.
Одним из важных этапов во многих задачах обработки голоса является разделение звукозаписи на отрезки не тишины, разделенные тишиной. Во избежание разбиения записи на слишком большое или слишком малое количество отрезков, тишина определяется как последовательность M сэмплов, где разница между наибольшим и наименьшим значением не превосходит заданного числа C.
Напишите программу, определяющую отрезки тишины в звукозаписи, состоящей из N сэмплов по известным параметрам M и C.
Первая строка содержит три целых числа: N (\(1\leq N \leq 1 000 000\)) — количество сэмплов в звукозаписи, M (\(1 \leq M \leq 10 000\)) — длину отрезка тишины и C (\(0 \leq C \leq 10 000\)) — максимальную разность значений для тишины.
Вторая строка содержит N чисел \(a_i\) (\(0 \leq a_i \leq 1 000 000\)) — сэмплы звукозаписи.
Выходной файл должен содержать все возможные значения i, такие, что max(a[i..i + m – 1]) – min(a[i..i + m – 1) \(\leq\) C. Значения должны быть выведены в порядке возрастания, каждое в отдельной строке.
Если ни одного отрезка тишины не существует, выведите слово NONE.
7 2 0 0 1 1 2 3 2 2
2 6
Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
\(N \leq 1500\)
\(N \leq 150\,000\)
Полные ограничения