Skip to content
This repository was archived by the owner on Jun 20, 2022. It is now read-only.

Latest commit

 

History

History
226 lines (177 loc) · 13 KB

File metadata and controls

226 lines (177 loc) · 13 KB

Структура данных

Машинки

Ограничение времени 1 секунда
Ограничение памяти 256Mb
Ввод стандартный ввод или input.in
Вывод стандартный вывод или output.out

Петя, которому три года, очень любит играть с машинками. Всего у Пети N различных машинок, которые хранятся на полке шкафа так высоко, что он сам не может до них дотянуться. Одновременно на полу комнаты может находиться не более K машинок. Петя играет с одной из машинок на полу и если он хочет поиграть с другой машинкой, которая также находится на полу, то дотягивается до нее сам. Если же машинка находится на полке, то он обращается за помощью к маме. Мама может достать для Пети машинку с полки и одновременно с этим поставить на полку любую машинку с пола. Мама очень хорошо знает своего ребенка и может предугадать последовательность, в которой Петя захочет играть с машинками. При этом, чтобы не мешать Петиной игре, она хочет совершить как можно меньше операций по подъему машинки с пола, каждый раз правильно выбирая машинку, которую следует убрать на полку. Ваша задача состоит в том, чтобы определить минимальное количество операций. Перед тем, как Петя начал играть, все машинки стоят на полке.

Формат ввода

В первой строке содержаться три числа N, K и P (1 ≤ K, N ≤ 100000, 1 ≤ P ≤ 500000). В следующих P строках записаны номера машинок в том порядке, в котором Петя захочет играть с ними.

Формат вывода

Выведите единственное число: минимальное количество операций, которое надо совершить Петиной маме.

Пример

IN                                          OUT

3 2 7                                       4
1
2
3
1
3
1
2

Гоблины и очереди

Ограничение времени 0.6 секунд
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt

Гоблины Мглистых гор очень любях ходить к своим шаманам. Так как гоблинов много, к шаманам часто образуются очень длинные очереди. А поскольку много гоблинов в одном месте быстро образуют шумную толку, которая мешает шаманам проводить сложные медицинские манипуляции, последние решили установить некоторые правила касательно порядка в очереди.

Обычные гоблины при посещении шаманов должны вставать в конец очереди. Привилегированные же гоблины, знающие особый пароль, встают ровно в ее середину, причем при нечетной длине очереди они встают сразу за центром.

Так как гоблины также широко известны своим непочтительным отношением ко всяческим правилам и законам, шаманы попросили вас написать программу, которая бы отслеживала порядок гоблинов в очереди.

Формат ввода

В первой строке входных данный записано число N (1 ≤ N ≤ 1e5) количество запросов. Следующие N строк содержат описание запросов в формате:

  • + i гоблин с номером i (1 ≤ i ≤ N) встаёт в конец очереди.
  • * i привилегированный гоблин с номером i встает в середину очереди.
  • - первый гоблин из очереди уходит к шаманам. Гарантируется, что на момент такого запроса очередь не пуста.

Формат вывода

Для каждого запроса типа - программа должна вывести номер гоблина, который должен зайти к шаманам.

Пример 1

IN                                          OUT

7                                           1
+ 1                                         2
+ 2                                         3
-
+ 3
+ 4
-
-

Пример 2

IN                                          OUT

2
* 1
+ 2

Менеджер памяти-1

Ограничение времени 1 секунда
Ограничение памяти 512Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt

Пете поручили написать менеджер памяти для новой стандартной библиотеки языка \varphi++. В распоряжении у менеджера находится массив из N последовательных ячеек памяти, пронумерованных от 1 до N. Задача менеджера – обрабатывать запросы приложений на выделение и освобождение памяти. Запрос на выделение памяти имеет один параметр K. Такой запрос означает, что приложение просит выделить ему K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом непосредственно перед самой первой ячейкой памяти выделяемого блока не должно располагаться свободной ячейки памяти. После этого выделенные ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется. Запрос на освобождение памяти имеет один параметр T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T – запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется. Требуется написать менеджер памяти, удовлетворяющий приведенным критериям.

Формат ввода

Первая строка входного файла содержит числа N и M – количество ячеек памяти и количество запросов соответственно (1 ≤ N ≤ 2^31-1; 1 ≤ M ≤ 1e5). Каждая из следующих M строк содержит по одному числу: i+1-я строка входного файла (1 ≤ i ≤ M) содержит либо положительное число K, если i-й запрос – запрос на выделение с параметром K (1 ≤ K ≤ N), либо отрицательное число -T, если i-й запрос – запрос на освобождение с параметром T (1 ≤ T < i).

Формат вывода

Для каждого запроса на выделение памяти выведите в выходной файл результат обработки этого запроса: для успешных запросов выведите номер первой ячейки памяти в выделенном блоке, для отклоненных запросов выведите число -1. Результаты нужно выводить в порядке следования запросов во входном файле.

Пример 1

IN                                          OUT

42 9                                        1
7                                           8
3                                           11
8                                           19
-2                                          25
6                                           30
5                                           19
-5
9
4

Пример 2

IN                                          OUT

128 12                                      1
1                                           2
2                                           4
4                                           8
-2                                          16
8                                           32
-3                                          64
16
-5
32
-7
64
-1

Минимум на отрезке

Ограничение времени 0.5 секунд
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt

Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается «окно» длины K, то есть сначала в «окне» видно первые K чисел, на следующем шаге в «окне» уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения «окна» определить минимум в нём.

Формат ввода

В первой строке входных данных содержатся два числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N) – длины последовательности и «окна», соответственно. На следующей строке находятся N чисел – сама последовательность. Числа последовательности не превосходят по модулю 1e5.

Формат вывода

Выходые данные должны содержать N-K+1 строк – минимумы для каждого положения «окна».

Пример

IN                                          OUT

7 3                                         1 2 2 3 1
1 3 2 4 5 3 1