Overview

We count the number of contiguous subsegments where the total cost of the canceled days equals the “total cost of all days \(- K\)”. Utilizing the fact that the cost for each day is positive, we can find this efficiently using the two-pointer technique.

Analysis

Focusing on the sum of the canceled subsegment

Let \(S = \sum_{i=1}^{N} A_i\) be the total cost of all days.

The condition for the cost to become \(K\) yen after canceling the interval \([l,r]\) is:

\(S - \sum_{i=l}^{r} A_i = K\)

Rearranging this gives:

\(\sum_{i=l}^{r} A_i = S-K\)

Therefore, let the target sum of the subsegment be \(T=S-K\).

First, we can divide the problem into cases depending on the value of \(T\):

• When \(T<0\)
  Even if all days are held, the total cost cannot reach \(K\) yen, so the answer is \(0\).
• When \(T=0\)
  If no days are canceled, the cost is exactly \(K\) yen. Furthermore, since \(A_i \ge 1\), canceling any non-empty subsegment will strictly decrease the cost. Therefore, the answer is \(1\).
• When \(T>0\)
  We find the number of non-empty contiguous subsegments whose sum is \(T\).

Checking all subsegments is too slow

There are \(\frac{N(N+1)}{2}\) contiguous subsegments. Even if we calculate the sum of each subsegment in \(O(1)\) time using prefix sums, checking all of them requires \(O(N^2)\) time.

Since \(N\) can be up to \(10^6\), this approach will exceed the time limit.

Utilizing the fact that each element is positive

Since \(A_i \ge 1\), the sum of a subsegment has the following properties:

• Moving the right endpoint to the right to add an element strictly increases the sum.
• Moving the left endpoint to the right to remove an element strictly decreases the sum.

From these properties, we can use the two-pointer technique, advancing the right pointer sequentially and advancing the left pointer only when the sum exceeds \(T\).

Moreover, for a fixed right endpoint, since the sum strictly decreases every time the left endpoint moves forward, there is at most \(1\) left endpoint for which the sum equals \(T\). Therefore, it suffices to check for an exact match once for each right endpoint.

Algorithm

1. Calculate \(T=\sum_{i=1}^{N} A_i-K\).
2. If \(T<0\), output \(0\); if \(T=0\), output \(1\), and terminate.
3. If \(T>0\), initialize the following variables:
   • left: the left endpoint of the current subsegment (\(0\)-indexed)
   • current: the sum of the current subsegment
   • answer: the number of subsegments satisfying the condition
4. Iterate through the elements of the array from left to right, adding each as the right endpoint of the subsegment:
   • Add the new element to current.
   • While current > T, subtract A[left] from current and increment left by \(1\).
   • If current == T, increment answer by \(1\).
5. Output answer.

Example

Consider the case where \(A=[1,2,1,2]\) and \(K=3\).

The overall sum is \(S=6\), so the target sum for the canceled subsegment is \(T=3\).

Day index added	Sum after addition	Subsegment after adjusting left pointer	Sum	Added to answer
\(1\)	\(1\)	\([1]\)	\(1\)	\(0\)
\(2\)	\(3\)	\([1,2]\)	\(3\)	\(1\)
\(3\)	\(4\)	\([2,1]\)	\(3\)	\(1\)
\(4\)	\(5\)	\([1,2]\)	\(3\)	\(1\)

There are \(3\) valid ways to cancel days, corresponding to the date intervals \([1,2]\), \([2,3]\), and \([3,4]\).

Why no valid subsegments are missed

When the sum of the subsegment exceeds \(T\), advancing the right endpoint further while keeping the same left endpoint will only increase the sum. Therefore, that left endpoint can never form a valid subsegment in the future, so it is safe to discard it.

On the other hand, once the sum becomes less than or equal to \(T\), advancing the left endpoint further would only make the sum strictly smaller. Thus, for that right endpoint, it is sufficient to check whether the current sum matches \(T\).

By doing this for every right endpoint, we can count all subsegments satisfying the condition without any omissions or duplicates.

Complexity

• Time Complexity: \(O(N)\)
  The right endpoint advances \(N\) times, and the left endpoint advances at most \(N\) times in total. Even with the while loop, the total number of operations across the entire algorithm is \(O(N)\).
• Space Complexity: \(O(N)\)
  Required to store the array A. The additional variables used for the two-pointer technique require \(O(1)\) space.

Implementation Notes

• Handle \(T=0\) beforehand.
  “Canceling nothing” constitutes \(1\) way. We handle this early to avoid erroneously counting empty subsegments at each right endpoint.

• Only advance the left pointer while the sum strictly exceeds the target.
  The condition is current > target. Be careful not to use >=, as we need to count the subsegment at the moment the sum equals the target.

• The subsegment may become empty.
  If a newly added element alone exceeds the target, advancing the left endpoint can make the sum \(0\). Since this process is only executed when \(T>0\), an empty subsegment will never be added to the answer.

• Be mindful of the magnitude of the sum.
  \(\sum A_i\) can be up to \(10^{15}\). While Python handles arbitrarily large integers automatically, languages with fixed-size integer types require \(64\)-bit integers.

• Use fast I/O since the input size is large.
  In the provided code, sys.stdin.buffer is used for reading input.

  Source Code

import sys


def main():
    input = sys.stdin.buffer
    N, K = map(int, input.readline().split())
    A = list(map(int, input.read().split()))

    target = sum(A) - K
    if target <= 0:
        print(1 if target == 0 else 0)
        return

    left = 0
    current = 0
    answer = 0

    for value in A:
        current += value
        while current > target:
            current -= A[left]
            left += 1
        if current == target:
            answer += 1

    print(answer)


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-6-astra-medium.