Б8103а. АиСД. Структуры данных

Задача A. Сбалансированное дерево ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	A. Klenin	Ограничение времени:	5 сек
Входной файл:	input.txt	Ограничение памяти:	200 Мб
Выходной файл:	output.txt

Условие

Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:

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

Формат входного файла

Входной файл содержит последовательность чисел.

Формат выходного файла

Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию.

Ограничения

Количество чисел находится в диапазоне от 0 до 10⁶, сами числа — в диапазоне от  − 2³¹ до 2³¹ − 1.

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`3 2 1 3 0`	`1 2 3`
2	`5 -1 6 -5 5 0`	`5 6`

Задача B. Сбалансированное дерево revisited ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	A. Klenin	Ограничение времени:	5 сек
Входной файл:	input.txt	Ограничение памяти:	256 Мб
Выходной файл:	output.txt

Условие

Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:

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

Формат входного файла

Входной файл содержит последовательность чисел.

Формат выходного файла

Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию.

Ограничения

Количество чисел находится в диапазоне от 0 до 10⁶, сами числа — в диапазоне от  − 2³¹ до 2³¹ − 1.

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`3 2 1 3 0`	`1 2 3`
2	`5 -1 6 -5 5 0`	`5 6`

Задача C. Антон и магазин радиодеталей ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	М. Спорышев, И. Блинов	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	512 Мб
Выходной файл:	output.txt

Условие

Инженер Антон зашёл в магазин радиодеталей. В магазине ровно N стеллажей. На i-м стеллаже лежат радиодетали типа a_i (на двух различных стеллажах тип радиодеталей может повторяться). Антон обходит с тележкой стеллажи в порядке от первого до N-го.

Когда Антон подходит к очередному стеллажу, он смотрит в тележку. Если в тележке нет радиодеталей такого типа, как на стеллаже, Антон берёт деталь со стеллажа и складывает в тележку. Если радиодеталь такого типа в тележке уже лежит, Антон просто идет дальше.

К сожалению, вместимость тележки ограничена K деталями. Поэтому, если тележка заполнена, а Антону необходимо выбрать, какую из имеющихся в тележке радиодеталей нужно убрать, прежде чем складывать новую деталь.

Антон знает заранее, какие типы радиодеталей лежат на стеллажах, и хочет каждый раз выбрасывать из тележки такую деталь, чтобы как можно меньше раз складывать новые радиодетали в тележку (складывает он их только в случае, если таких деталей в тележке нет на данный момент).

Помогите Антону узнать, какое минимальное количество раз ему придётся складывать новую деталь в тележку.

Примечание

Рекомендуется рассмотреть частичные решения для N ≤ 1000, a_i ≤ 10⁵.

Формат входного файла

Входной файл содержит целое число два целых числа N и K, вторая строка содержит N чисел a_i.

Формат выходного файла

Выходной файл должен содержать единственное число — минимальное количество раз, которое придётся положить деталь в тележку.

Ограничения

1 ≤ N, K ≤ 10⁵

0 ≤ a_i ≤ 10⁹

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`3 3 1 2 3`	`3`
2	`5 2 1 1 1 2 2`	`2`
3	`7 3 8 2 3 1 1 2 2`	`4`