Самый дешёвый тариф
Сервис сравнивает тарифы. У тарифа есть абонентская плата a тенге в месяц и цена b тенге за единицу расхода: при расходе x месяц стоит a + b · x. Тарифы появляются по одному, вперемешку с вопросами «сколько заплатит за месяц человек с расходом x, если выберет самый выгодный из уже появившихся тарифов?».
Вход
В первой строке — число событий q (1 ≤ q ≤ 10⁵). Дальше q строк: add a b — появился тариф (0 ≤ a ≤ 10⁹, 0 ≤ b ≤ 10⁶), или ask x — вопрос (0 ≤ x ≤ 10⁶).
Выход
На каждый вопрос — наименьшая цена месяца или -, если тарифов ещё нет.
Примеры
Пример 1
8 ask 5 add 2000 30 ask 100 add 5000 5 ask 100 ask 200 add 0 60 ask 50
- 5000 5000 6000 3000
Пример 2
4 add 100 10 add 100 10 ask 0 ask 1000000
100 10000100
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Тариф — прямая y = a + bx, ответ — нижняя огибающая прямых в точке x. Почему здесь не годится дек из статьи?
2Подсказка 2
Наклоны приходят в любом порядке, а вопросы — в любых точках и вперемешку с новыми тарифами. Нужна структура, куда прямую можно добавить в любой момент, а минимум в точке — узнать за логарифм. Точки x — целые от 0 до 10⁶.
3Идея
Дерево Ли Чао над отрезком [0, 2²⁰). Узел хранит прямую, которая ниже в середине его отрезка. Две прямые пересекаются не больше раза, поэтому проигравшая в середине может выиграть только на одной половине — туда она и спускается. Ответ в точке — минимум прямых на пути от корня к листу.
4Разбор
Дерево — массивы на 2 · 2²⁰ узлов, как у дерева отрезков с корнем 1. Вставка: если узел пуст — кладём прямую; иначе сравниваем в середине и меняем местами, если новая ниже; затем смотрим на концы отрезка: где проигравшая ниже, туда и спускаемся, а если ни на одном конце — она нигде не нужна. Вопрос: идём к листу x, пока узлы не пусты, и берём минимум.
4+Решение
5Сложность
O(log C) на событие, C = 2²⁰: двадцать уровней. Цена не больше 10⁹ + 10¹² — помещается в 64 бита.
6Типичные ошибки
- Перебрать все тарифы. Это
wrong.py: при пятидесяти тысячах тарифов и стольких же вопросах — больше миллиарда умножений, и в третьем тесте времени не хватает. - Дек с отсортированными наклонами. Тарифы приходят вперемешку с вопросами, и отсортировать их заранее нельзя.
- Сравнение не в той точке. Решать, куда спускаться, нужно по концам отрезка узла (или по знаку разности в середине и на одном конце), иначе проигравшая прямая уйдёт не в ту половину.
- Пустое дерево. Вопрос до первого тарифа —
-, а не ноль и не «бесконечность».