--->
14 задач
<---
Источники
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes
В баре у Мо дела идут как всегда прекрасно. Чтобы дела шли еще лучше, Мо озадачился вопросом разнообразия сортов пива, которые разливают в его баре. Для составления стратегического плана по улучшению списка сортов пива Мо должен получить ответы на ряд вопросов.
В данный момент у барной стойки сидят \(n\) посетителей и у каждого посетителя есть кружка с пивом одного из сортов. Мо пронумеровал посетителей слева направо числами от \(1\) до \(n\). После этого он пронумеровал сорта пива числами от \(1\) до \(m\). Далее Мо вспомнил число \(k\), которое было рекомендовано в гороскопе на эту неделю. Наконец, Мо составил список из \(q\) вопросов, ответы на которые помогут его бизнесу стать еще успешней. В каждом вопросе спрашивается следующее: каково количество сортов пива, которые можно встретить ровно \(k\) раз в кружках посетителей с номерами от \(l\) до \(r\) включительно.
Входные данные
В первой строке даны четыре целых числа \(n\), \(m\), \(q\) и \(k\) (\(1 \le n, \ q \le 2 \cdot 10^5\), \(1 \le m \le 10^6\), \(0 \le k \le 3\)).
Во второй строке даны \(n\) целых чисел \(1 \le a_1, \ldots, a_n \le m\) -- номера сортов пива у посетителей.
В следующих \(q\) строках заданы по два целых числа \(l\) и \(r\), которые задают запрос для посетителей с номерами от \(l\) до \(r\) (\(1 \le l \le r \le n\)).
Выходные данные
Для каждого запроса выведите в отдельной строке количество сортов пива, которые на отрезке от \(l\) до \(r\) встречаются ровно \(k\) раз.
Примеры
Входные данные
5 5 2 2 1 2 2 1 5 1 5 2 4
Выходные данные
2 1
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
256 megabytes
В баре у Мо дела идут по-прежнему прекрасно. Как известно, чтобы дела шли еще лучше, Мо озадачился вопросом разнообразия сортов пива, которые разливают в его баре. Для составления стратегического плана по улучшению списка сортов пива Мо должен получить ответы на ряд вопросов.
В данный момент у барной стойки сидят \(n\) посетителей и у каждого посетителя есть кружка с пивом одного из сортов. Мо пронумеровал посетителей слева направо числами от \(1\) до \(n\). После этого он пронумеровал сорта пива числами от \(1\) до \(m\). Далее Мо вспомнил число \(k\), которое было рекомендовано в гороскопе на эту неделю. Наконец, Мо составил список вопросов, ответы на которые помогут его бизнесу стать еще успешней. В каждом вопросе спрашивается следующее: каково количество сортов пива, которые можно встретить ровно \(k\) раз в кружках посетителей с номерами от \(l\) до \(r\) включительно.
Мо ответил на все вопросы, но вдруг заметил, что пока он отвечал на вопросы, некоторые посетители выпивали свое пиво и тут же заказывали новую кружку с пивом, возможно другого сорта.
Чтобы проверить правильно ли Мо ответил на все вопросы, напишите программу которая ответит на все вопросы, учитывая все заказы посетителей. Всего в сумме произошло \(q\) событий, каждое из которых либо смена кружки пива одним из посетителей или вопрос от Мо.
Входные данные
В первой строке даны четыре целых числа \(n\), \(m\), \(q\) и \(k\) (\(1 \le n, \ q \le 10^5\), \(1 \le m \le 10^6\), \(0 \le k \le 3\)).
Во второй строке даны \(n\) целых чисел \(1 \le a_1, \ldots, a_n \le m\) -- номера сортов пива у посетителей.
В следующих \(q\) строках заданы события. Каждое событие одного из двух типов:
\(1 \ l \ r\) -- вопрос от Мо (\(1 \le l \le r \le n\)).
\(2 \ i \ j\) -- \(i\)-й посетитель перешел на пиво сорта \(j\), (\(1 \le i \le n\), \(1 \le j \le m\)).
Выходные данные
Для каждого запроса первого типа выведите в отдельной строке ответ на него.
Примеры
Входные данные
5 5 3 2 1 2 2 1 5 1 1 5 2 3 3 1 1 5
Выходные данные
2 1
ограничение по времени на тест
1.5 second;
ограничение по памяти на тест
256 megabytes
Дан массив чисел и натуральное число \(K\). Над ним проделывают следующую операцию: выбирают числа, стоящие на позициях, кратных \(K\) (т.е. на позициях \(0\), \(K\), \(2K\) и т.д.), находят максимальное среди них число и удаляют его из исходного массива. Если максимумов несколько, то выбирают первый из них. После удаления все числа, стоящие правее него, смещаются на одну позицию влево. Операцию повторяют, пока все числа не кончатся.
Напишите программу, которая выведет числа в порядке их удаления.
Входные данные
Первая строка содержит натуральные числа \(N\) и \(K\) \((2 \le K \le N \le 100000)\).
Вторая строка содержит \(N\) натуральных чисел из отрезка \([1, N]\).
Выходные данные
Выведите \(N\) натуральных чисел, \(i\)-е из которых равно числу, удалённому на \(i\)-м шаге.
Система оценки
В задаче 5 подгрупп:
- (7 баллов) Ограничения: \(N \le 1000\)
- (25 баллов) Ограничения: \(K = 2\)
- (23 балла) Ограничения: \(K \le 10\)
- (25 баллов) Ограничения: \(100 \le K \le N\)
- (20 баллов) Без дополнительных ограничений.
Примеры
Входные данные
10 2 2 3 1 9 10 4 5 6 1 5
Выходные данные
10 6 4 5 2 9 3 5 1 1
Входные данные
10 3 2 3 1 9 10 4 5 6 1 5
Выходные данные
9 10 4 5 6 2 5 3 1 1
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes
Байтазар планирует заняться производством солнечных панелей. Он получил \(n\) заказов, каждый заказ характеризуется минимальной \(w_{min}\) и максимальной \(w_{max}\) шириной солнечной панели, а также минимальной \(l_{min}\) и максимальной \(l_{max}\) длиной солнечной панели. Выполняя заказ, Байтзар может изготовить солнечную панель любого размера \(a \times b\), такого что \(w_{min} \le a \le w_{max}, l_{min} \le b \le l_{max}\). Солнечная панель состоит из квадратных ячеек. Ячейка может иметь любой размер \(c \times c\), где \(c\) — целое число. Байтазар хотел бы использовать для каждого заказа как можно большие по размеру ячейки. Помогите ему найти для каждого заказа максимальное \(c\), такое что он сможет выполнить заказ, используя ячейки \(c \times c\).
Входные данные
Первая строка ввода содержит число \(n\) (\(1 \le n \le 1000\)) — количество заказов. Следующие \(n\) строк содержит по четыре целых числа \(w_{min}, w_{max}, l_{min}, l_{max}\) и описывают заказы (\(1 \le w_{min} \le w_{max} \le 10^9, 1 \le l_{min} \le l_{max} \le 10^9\) ).
Выходные данные
Для каждого заказа выведите одно число: максимальную длину стороны квадратной ячейки, из которых можно изготовить панель для этого заказа.
Система оценки
Подзадача 1 (10 баллов): \(1 \le n \le 10\)
Подзадача 2 (40 баллов): \(1 \le l_{max}, w_{max} \le 10 ^ 7\)
Подзадача 3 (50 баллов): Нет дополнительных ограничений. Зависит от подзадач 1 и 2.
Примеры
Входные данные
4 3 9 8 8 1 10 11 15 4 7 22 23 2 5 19 24
Выходные данные
8 7 2 5
Выбрано
:
|