Баланс по чекам

После походов в магазин у тебя есть список дневных изменений баланса: где-то деньги потратил (отрицательное число), где-то вернули сдачу или пришёл кэшбэк (положительное число).

Тебе интересно, сколько существует подряд идущих отрезков дней, на которых суммарное изменение баланса ровно равно заданному числу S.

Важно: числа могут быть отрицательными, а суммы могут не помещаться в 32-битный тип (используй 64-битные целые; в Python это не проблема).

Формат ввода

В первой строке два целых числа n и S — количество дней и целевая сумма. Во второй строке n целых чисел a1, a2, ..., an — изменения баланса по дням.

Формат вывода

Выведи одно целое число — количество подотрезков (непустых, состоящих из подряд идущих дней), сумма на которых равна S.

Ограничения

• 1 ≤ n ≤ 20000
• -100000 ≤ ai ≤ 100000
• |S| ≤ 1000000000
• Все вычисления суммы могут выходить за 32-битный диапазон.

Пример

Ввод:

5 3
1 2 1 -1 3

Вывод:

5

Ключевое наблюдение: сумма на отрезке l..r равна pref[r] - pref[l-1], где pref[i] — сумма первых i дней. Тогда условие sum(l..r) = S превращается в pref[l-1] = pref[r] - S.

Почему работает приём: если идти слева направо и знать, сколько раз уже встречалась каждая префиксная сумма, то для текущего правого конца r мы мгновенно узнаём, сколько подходящих l существует — это ровно частота значения pref[r] - S.

План решения:

• Заведи pref = 0 и словарь cnt, где cnt[p] = сколько раз префиксная сумма p уже встречалась.
• Важно: положи cnt[0] = 1 (пустой префикс до начала массива).
• Для каждого элемента x:
• обнови pref += x;
• посчитай, сколько отрезков заканчиваются здесь: добавь cnt.get(pref - S, 0) к ответу;
• увеличь cnt[pref] на 1.
• Выведи ответ.

Мини-сниппет логики шага: ans += cnt.get(pref - S, 0).

Сложность: O(n) по времени и O(n) по памяти (в худшем случае все префиксы разные), что сильно лучше O(n^2) перебора всех отрезков.

Частая ошибка: забыть про cnt[0] = 1 — тогда не посчитаются отрезки, начинающиеся с первого дня.