🟠 Middle — массивы#
Четыре авторские задачи на скользящее окно, префиксные суммы, слияние и компактную работу с памятью.
1. Удаление устаревших измерений#
В журнале датчика записаны значения. Удалите все значения, меньшие порога X, сохранив порядок оставшихся. Сдвигайте элементы внутри исходного массива, не создавая второй массив.
Ввод: N X (1 ≤ N ≤ 2·10^5, -10^9 ≤ X ≤ 10^9), затем N целых чисел a_i (|a_i| ≤ 10^9).
Вывод: количество оставшихся значений, затем сами значения. Если ни одного не осталось, выведите только 0.
Пример:
7 5
8 2 5 1 9 4 7
4
8 5 9 7
Требование: O(N) времени и O(1) дополнительной памяти. Подумайте, почему удалять элементы по одному из середины вектора невыгодно.
2. Суммы отрезков#
Дан массив расходов за N дней и Q запросов. Для каждого запроса найдите сумму расходов на отрезке от L до R включительно. Индексы во входе начинаются с единицы.
Ввод: N Q (1 ≤ N,Q ≤ 2·10^5), затем N неотрицательных чисел не больше 10^9, затем Q пар L R (1 ≤ L ≤ R ≤ N).
Вывод: для каждого запроса выведите сумму на отдельной строке.
Пример:
5 3
2 4 1 7 3
1 3
2 5
4 4
7
15
7
Требование: O(N+Q) времени. Используйте префиксные суммы типа long long; массив префиксов занимает O(N) дополнительной памяти.
3. Слияние двух журналов#
Даны два отсортированных по неубыванию массива временных меток. Объедините их в один отсортированный массив. При равных значениях сначала берите элемент из первого массива.
Ввод: N M (0 ≤ N,M ≤ 2·10^5), затем N чисел первого массива и M чисел второго; значения по модулю не превосходят 10^9.
Вывод: N+M чисел объединённого массива.
Пример:
4 3
1 4 4 9
2 4 8
1 2 4 4 4 8 9
Требование: O(N+M) времени. Результат неизбежно занимает O(N+M) памяти; избегайте повторных вставок в начало вектора.
4. Самое длинное окно бюджета#
Для каждого дня известна стоимость покупок. Найдите максимальную длину непрерывного отрезка дней, на котором суммарная стоимость не превосходит бюджета B. Все стоимости неотрицательны.
Ввод: N B (1 ≤ N ≤ 2·10^5, 0 ≤ B ≤ 10^18), затем N чисел a_i (0 ≤ a_i ≤ 10^9).
Вывод: максимальная длина подходящего отрезка. Пустой отрезок допустим, поэтому ответ может быть 0.
Пример:
6 7
2 1 3 2 1 4
4
Требование: O(N) времени и O(1) дополнительной памяти после чтения входных значений.