Олимпиада Ломоносов 2022-2023 Отборочный тур Задача 4 Измерения температуры 2024-11-06

Разбираем тему стека (дека) рекордов.

Ассоциация репетиторов https://repetit.ru/repetitor.aspx?id=43394
Моя анкета на профи ру https://profi.ru/profile/SabitovRSh/
Мой вк https://vk.com/sabitoff
Группа вк https://vk.com/mgu_5
Задача взяты с сайта https://olymp.msu.ru/rus/page/main/29/page/zadaniya-olimpiady-proshlyh-let
Ссылка на архив https://olympiads.msu.ru/uploads/lom22_23/tasks/%D0%9B%D0%9E%D0%9C-2022-2023-%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D1%8F-%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0.zip

Условие
Задача 4. Измерения температуры
В результате измерения были получены среднедневные температуры за N последовательных
дней (1 ≤ N ≤ 107). Иннокентий решил найти максимальную температуру на всех последова-
тельных интервалах длины K (1 ≤ K ≤ 104, K ≤ N). То есть, на отрезках [0..K − 1], [1..K],
[2..K + 1] и т. д.. Результаты поисков не понравились Иннокентию, поэтому он решил расши-
рить слева и справа каждый i-й отрезок на li, ri соответственно. Считайте, что если при этом
происходит выход за границы исходной последовательности, то числа там −inf. На стандартном
потоке вводится число N и N чисел, задающих последовательность измерений. Затем следует K
– длина отрезка поиска, затем следуют N − K + 1 пары положительных чисел, не больших 1000
и не больших K, – li, ri соответственно.
Для каждого из N − K + 1 отрезков длины K c соответствующими расширениями выведите
максимум на них.
Пример:
Ввод:
10
1 2 3 1 3 7 8 5 3 1
3
0 1
1 1
0 1
0 0
0 0
0 0
0 0
1 0
Вывод:
3
3
7
7
8
8
8
8

Видео Олимпиада Ломоносов 2022-2023 Отборочный тур Задача 4 Измерения температуры 2024-11-06 канала Rodion Sabitov