Ctrl K

Журнал маяков

Средняя
Спасатели расставляют маяки на бесконечной клетчатой равнине, штаб стоит в точке (0, 0). Список points — порядок установки: points[i] = [x, y] значит, что i-м по счёту маяк поставили в точку (x, y). Все точки различны. Расстояние от штаба до маяка в точке (x, y) считается как |x| + |y|. После каждой установки штаб записывает в журнал расстояние до rank-го по близости маяка среди уже стоящих (при равных расстояниях каждый маяк считается отдельно). Если маяков пока меньше rank, записывается -1. Верните журнал — список из len(points) чисел.
Пример 1
points=[[2, -1], [0, 5], [-1, 0], [4, 4]], rank=2 → [-1, 5, 3, 3]

Расстояния появляются по очереди: 3, 5, 1, 8. После первого маяка второго по близости нет (-1), дальше второе по возрастанию: 5, 3, 3.

Пример 2
points=[[6, 0], [-3, -3], [0, 1]], rank=1 → [6, 6, 1]

При rank = 1 это просто ближайший маяк на каждый момент: 6, затем 6 (у второго тоже 6), затем 1.

Ограничения
  • 1 ≤ len(points) ≤ 2·10⁵
  • -10⁹ ≤ x, y ≤ 10⁹
  • Все точки различны
  • 1 ≤ rank ≤ 10⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиK-й результат сверху СредняяСтудии для записи СредняяСамые частые значения СредняяСамые лёгкие пары СредняяK-е по величине в упорядоченной таблице Средняя
загружаем Python…
Вход
points=[[2, -1], [0, 5], [-1, 0], [4, 4]], rank=2
Ожидается
[-1, 5, 3, 3]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 86 тестов на сервере, включая скрытые.