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

108. Сколько посылок легче идут следом

Сложная

На сортировочной ленте склада Ozon посылки едут в порядке weights — вес каждой в граммах. Манипулятор снимает посылку и ставит её поверх тех, что едут следом и легче неё: так тяжёлые не давят лёгкие.

Для каждой позиции i посчитайте, сколько посылок правее неё строго легче weights[i].

Верните список той же длины.

В работе: Оценка, сколько перекладываний сделает манипулятор на каждую посылку.

Пример 1

Ввод
weights = [500, 200, 600, 100]
Вывод
[2, 1, 1, 0]

За 500 г едут 200 и 100 — две легче. За 600 — только 100.

Пример 2

Ввод
weights = [300, 300, 300]
Вывод
[0, 0, 0]

Одинаковый вес не считается: нужно строго легче.

Ограничения

  • 0 ≤ n ≤ 10⁵
  • 1 ≤ weights[i] ≤ 10⁹
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def lighter_behind(weights):
Дерево ФенвикаСжатие координатцельO(n log n)

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