Overview

If the total cost of the entire trip is \(S\) yen, we only need to cancel a contiguous subsegment with a sum of \(S-K\) yen. Since the cost of each day is positive, we can count such subsegments 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 the entire trip.

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

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

Rearranging this gives:

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

In other words, the problem can be rephrased as finding the number of contiguous subsegments whose sum is \(S-K\).

However, we handle the following edge cases first:

• If \(S<K\): Since canceling plans will never increase the cost, the answer is \(0\).
• If \(S=K\): Only the option of canceling nothing satisfies the condition, so the answer is \(1\). Since all \(A_i\) are positive, canceling even a single day will make the cost strictly less than \(K\).

From here on, we assume \(S>K\) and define the target subsegment sum as \(T=S-K>0\).

Checking all subsegments is too slow

There are \(\frac{N(N+1)}{2}\) contiguous subsegments. Even if we use prefix sums to compute each subsegment sum in \(O(1)\) time, checking all of them would take \(O(N^2)\) time.

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

Utilizing the property that each element is positive

Since all \(A_i\) are positive, the subsegment sum has the following properties:

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

Therefore, we can use the two-pointer technique: move the right endpoint forward one by one, and advance the left endpoint only when the subsegment sum exceeds \(T\).

Once a left endpoint is ruled out because the subsegment sum is already too large, extending the right endpoint further will only increase the sum, so we never need to reconsider that left endpoint.

Furthermore, for a fixed right endpoint, advancing the left endpoint strictly decreases the subsegment sum, so there is at most one left endpoint that yields a sum equal to \(T\).

Algorithm

To align with standard implementation, we use \(0\)-based indexing for the array.

1. Read the array and compute the total sum \(S\).
2. If \(S<K\), output \(0\); if \(S=K\), output \(1\), and terminate.
3. Set \(T=S-K\), and initialize the left endpoint left, the subsegment sum sum, and the answer answer all to \(0\).
4. Iterate the right endpoint right from \(0\) to \(N-1\):
   • Add A[right] to sum.
   • While sum > T, subtract A[left] from sum and increment left by \(1\).
   • If sum == T, this subsegment can be canceled, so increment answer by \(1\).
5. Output answer.

Concrete Example

Let \(A=(1,2,1,3)\) and \(K=4\).

The total sum is \(S=7\), so we look for subsegments with a sum of \(T=7-4=3\).

Element added	Sum right after addition	Subsegment after adjusting left endpoint	Counted?
\(1\)	\(1\)	\((1)\)	No
\(2\)	\(3\)	\((1,2)\)	Yes
\(1\)	\(4\)	\((2,1)\)	Yes
\(3\)	\(6\)	\((3)\)	Yes

There are \(3\) valid ways to cancel plans: days 1–2, days 2–3, and day 4.

Why This Correctly Counts the Subsegments

For each right endpoint, as long as the subsegment sum exceeds \(T\), the subsegment cannot be part of the answer, so we advance the left endpoint. Discarded left endpoints will yield even larger sums as the right endpoint moves further to the right, so they can never be candidates in the future.

If the subsegment sum after adjustment is \(T\), we count that subsegment. If it is less than \(T\), advancing the left endpoint further would only decrease the sum, so no valid subsegment exists for this right endpoint.

Thus, all subsegments satisfying the condition are counted without omissions or duplicates.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Although there is a while loop, the left pointer advances at most \(N\) times in total across the entire process. The right pointer also moves only \(N\) times, resulting in an overall time complexity of \(O(N)\).

Storing the array A requires \(O(N)\) space. The auxiliary space other than the array is \(O(1)\).

Implementation Points

• Use 64-bit integers for sums
  The total sum can be up to \(10^6\times 10^9=10^{15}\). Use C++’s long long for total, K, target, and sum.

• Handle \(S=K\) before applying the two-pointer technique
  There is \(1\) way to “cancel nothing”. If you set the target sum to \(0\) and count empty subsegments, you risk counting the same option multiple times.

• The condition to advance the left pointer is sum > target
  When they are equal, the subsegment satisfies the condition, so we count it without shrinking it.

• The subsegment may become empty
  If the newly added element alone exceeds target, after adjustment we will have left == right + 1 and sum == 0. However, since target > 0, an empty subsegment will never be counted toward the answer.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    cin >> N >> K;

    vector<int> A(N);
    long long total = 0;
    for (int &a : A) {
        cin >> a;
        total += a;
    }

    if (total < K) {
        cout << 0 << '\n';
        return 0;
    }
    if (total == K) {
        cout << 1 << '\n';
        return 0;
    }

    const long long target = total - K;
    long long sum = 0, answer = 0;
    int left = 0;

    for (int right = 0; right < N; ++right) {
        sum += A[right];
        while (sum > target) {
            sum -= A[left++];
        }
        if (sum == target) {
            ++answer;
        }
    }

    cout << answer << '\n';
    return 0;
}

---

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