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

212. Отрезки операций с суммой в коридоре

Сложная

В выписке по счёту в СберБизнесе операции идут подряд: ops[i] в рублях, поступления положительные, списания отрицательные.

Посчитайте, сколько непустых отрезков подряд идущих операций дают в сумме число от lo до hi включительно.

В работе: Финмониторинг ищет серии операций, которые вместе укладываются в коридор 590–600 тыс. ₽ — чуть ниже внутреннего порога ручной проверки. В выписке за квартал 50 000 операций, отрезков — 1,25 млрд.

Пример 1

Ввод
ops = [300, -100, 400, 200, -500]
lo = 300
hi = 600
Вывод
7

Подходят [300], [300, −100, 400], [−100, 400], [400], [400, 200], [300, −100, 400, 200, −500], [−100, 400, 200, −500].

Пример 2

Ввод
ops = [5]
lo = 6
hi = 10
Вывод
0

Ограничения

  • 1 ≤ n ≤ 10⁵
  • −10⁶ ≤ ops[i] ≤ 10⁶
  • −10¹¹ ≤ lo ≤ hi ≤ 10¹¹
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def sums_in_corridor(ops, lo, hi):
Префиксные суммыСортировка слияниемРазделяй и властвуйцельO(n log n)

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