Войти Регистрация
Алгоритмы

109. k-я по дешевизне цена в рубрике

Сложная

В рубрике Авито «Велосипеды» объявления публикуют и снимают. Операции идут списком ops:

["add", p] — опубликовали объявление с ценой p рублей; ["remove", p] — сняли одно объявление с ценой p (гарантируется, что такое есть);

["kth", k] — k-я по возрастанию цена среди активных объявлений, повторы считаются отдельно. Если активных меньше k, ответ −1.

Верните список ответов на запросы kth по порядку. Так виджет «дешевле, чем 80 % похожих» берёт порог без сортировки всей рубрики.

В работе: Порог цены для плашки «хорошая цена» по живой рубрике.

Пример 1

Ввод
ops = [["add", 15000], ["add", 9000], ["add", 15000], ["kth", 2], ["remove", 9000], ["kth", 2], ["kth", 3]]
Вывод
[15000, 15000, -1]

Сначала цены 9000, 15000, 15000 — вторая 15000. После снятия их две, третьей нет: −1.

Пример 2

Ввод
ops = [["kth", 1]]
Вывод
[-1]

Пустая рубрика.

Ограничения

  • 0 ≤ длина ops ≤ 10⁵
  • 1 ≤ p ≤ 10⁶, 1 ≤ k ≤ 10⁵
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def kth_cheapest(ops):
Дерево ФенвикаПорядковая статистикацельO(n log n)

Источник: наша задача на данных Авито. Условие пересказано своими словами.