Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается «окно» длины K, то есть сначала в «окне» видно первые K чисел, на следующем шаге в «окне» уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения «окна» определить минимум в нём.
В первой строке входных данных содержатся два числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N) – длины последовательности и «окна», соответственно. На следующей строке находятся N чисел – сама последовательность. Числа последовательности не превосходят по модулю 10^5.
Выходые данные должны содержать N - K + 1 строк – минимумы для каждого положения «окна».
| Ввод | Вывод |
|---|---|
| 7 3 | 1 2 2 3 1 |
| 1 3 2 4 5 3 1 |
Гоблины Мглистых гор очень любях ходить к своим шаманам. Так как гоблинов много, к шаманам часто образуются очень длинные очереди. А поскольку много гоблинов в одном месте быстро образуют шумную толку, которая мешает шаманам проводить сложные медицинские манипуляции, последние решили установить некоторые правила касательно порядка в очереди.
Обычные гоблины при посещении шаманов должны вставать в конец очереди. Привилегированные же гоблины, знающие особый пароль, встают ровно в ее середину, причем при нечетной длине очереди они встают сразу за центром.
Так как гоблины также широко известны своим непочтительным отношением ко всяческим правилам и законам, шаманы попросили вас написать программу, которая бы отслеживала порядок гоблинов в очереди.
В первой строке входных данный записано число N (1 ≤ N ≤ 10^5) количество запросов. Следующие N строк содержат описание запросов в формате:
- + i гоблин с номером i (1 ≤ i ≤ N) встаёт в конец очереди.
- * i привилегированный гоблин с номером i встает в середину очереди.
- - первый гоблин из очереди уходит к шаманам. Гарантируется, что на момент такого запроса очередь не пуста.
Для каждого запроса типа - программа должна вывести номер гоблина, который должен зайти к шаманам.
| Ввод | Вывод |
|---|---|
| 7 | 1 |
| + 1 | 2 |
| + 2 | 3 |
| - | |
| + 3 | |
| + 4 | |
| - | |
| - |
| Ввод | Вывод |
|---|---|
| 2 | |
| * 1 | |
| + 2 |
Петя, которому три года, очень любит играть с машинками. Всего у Пети N различных машинок, которые хранятся на полке шкафа так высоко, что он сам не может до них дотянуться. Одновременно на полу комнаты может находиться не более K машинок. Петя играет с одной из машинок на полу и если он хочет поиграть с другой машинкой, которая также находится на полу, то дотягивается до нее сам. Если же машинка находится на полке, то он обращается за помощью к маме. Мама может достать для Пети машинку с полки и одновременно с этим поставить на полку любую машинку с пола. Мама очень хорошо знает своего ребенка и может предугадать последовательность, в которой Петя захочет играть с машинками. При этом, чтобы не мешать Петиной игре, она хочет совершить как можно меньше операций по подъему машинки с пола, каждый раз правильно выбирая машинку, которую следует убрать на полку. Ваша задача состоит в том, чтобы определить минимальное количество операций. Перед тем, как Петя начал играть, все машинки стоят на полке.
В первой строке содержаться три числа N, K и P (1≤ K, N ≤ 100000, 1≤ P ≤ 500000). В следующих P строках записаны номера машинок в том порядке, в котором Петя захочет играть с ними.
Выведите единственное число: минимальное количество операций, которое надо совершить Петиной маме.
| Ввод | Вывод |
|---|---|
| 3 2 7 | 4 |
| 1 | |
| 2 | |
| 3 | |
| 1 | |
| 3 | |
| 1 | |
| 2 |
| Ввод | Вывод |
|---|---|
| 10 3 20 | 11 |
| 1 | |
| 2 | |
| 3 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 4 | |
| 3 | |
| 5 | |
| 1 | |
| 5 | |
| 6 | |
| 8 | |
| 10 | |
| 9 | |
| 8 | |
| 9 | |
| 10 | |
| 6 |
В этой задаче можно использовать STL.
Пояснения к примеру 1:
Операция 1: снять машинку 1
Операция 2: снять машинку 2
Операция 3: поднять машинку 2 и снять машинку 3
Операция 4: поднять машинку 3 или 1 и снять машинку 2
Пете поручили написать менеджер памяти для новой стандартной библиотеки языка \varphi++. В распоряжении у менеджера находится массив из N последовательных ячеек памяти, пронумерованных от 1 до N. Задача менеджера – обрабатывать запросы приложений на выделение и освобождение памяти. Запрос на выделение памяти имеет один параметр K. Такой запрос означает, что приложение просит выделить ему K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом непосредственно перед самой первой ячейкой памяти выделяемого блока не должно располагаться свободной ячейки памяти. После этого выделенные ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется. Запрос на освобождение памяти имеет один параметр T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T – запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется. Требуется написать менеджер памяти, удовлетворяющий приведенным критериям.
Первая строка входного файла содержит числа N и M – количество ячеек памяти и количество запросов соответственно (1 ≤ N ≤ 2^31 - 1; 1 ≤ M ≤ 10^5). Каждая из следующих M строк содержит по одному числу: (i+1)-я строка входного файла (1 ≤ i ≤ M) содержит либо положительное число K, если i-й запрос – запрос на выделение с параметром K (1 ≤ K ≤ N), либо отрицательное число -T, если i-й запрос – запрос на освобождение с параметром T (1 ≤ T < i).
Для каждого запроса на выделение памяти выведите в выходной файл результат обработки этого запроса: для успешных запросов выведите номер первой ячейки памяти в выделенном блоке, для отклоненных запросов выведите число -1. Результаты нужно выводить в порядке следования запросов во входном файле.
| Ввод | Вывод |
|---|---|
| 42 9 | 1 |
| 7 | 8 |
| 3 | 11 |
| 8 | 19 |
| -2 | 25 |
| 6 | 30 |
| 5 | 39 |
| -5 | |
| 9 | |
| 4 |
| Ввод | Вывод |
|---|---|
| 128 12 | 1 |
| 1 | 2 |
| 2 | 4 |
| 4 | 8 |
| -2 | 16 |
| 8 | 32 |
| -3 | 64 |
| 16 | |
| -5 | |
| 32 | |
| -7 | |
| 64 | |
| -1 |
| Ввод | Вывод |
|---|---|
| 2000000000 9 | 1 2000000000 -1 1 -1 -1 |
| 1999999999 1 2 -3 -1 1999999999 1 -7 1 |
| Ввод | Вывод |
|---|---|
| 16 40 | 1 5 9 13 -1 -1 1 1 1 1 1 13 1 1 4 9 1 4 9 1 |
| 4 4 4 4 4 4 -1 -2 1 -9 -3 -4 -5 -6 15 -15 16 -17 10 -19 12 4 -21 12 -22 -24 3 5 8 -28 -27 -29 3 5 7 -33 -35 -34 16 -39 |