Overview

This problem asks you to find the number of contiguous subarrays \((l, r)\) of a sequence \(A\) of length \(N\) such that the length is at least \(K\) and the sum of the interval multiplied by \(C\) is at most \(T\).

Analysis

1. Simplifying the Expression

The condition in the problem is \(C \times (A_l + A_{l+1} + \cdots + A_r) \leq T\). Rearranging this gives: $\(A_l + A_{l+1} + \cdots + A_r \leq \lfloor \frac{T}{C} \rfloor\)\( (Since \)A_i\( are integers, using floor division on the right-hand side is valid.) By precomputing \)M = \lfloor \frac{T}{C} \rfloor\(, the condition simplifies to "the sum of the interval is at most \)M$“.

2. Limitations of the Naive Approach

If we naively check all pairs \((l, r)\), there are \(O(N^2)\) such pairs, resulting in an overall time complexity of \(O(N^2)\). Given the constraint \(N \leq 2 \times 10^6\), an \(O(N^2)\) solution will not fit within the time limit and will result in TLE (Time Limit Exceeded). Therefore, we need to consider a faster \(O(N)\) approach.

3. Exploiting Monotonicity with the “Two Pointers” Technique

All elements of the array \(A\) are integers of at least \(1\). Therefore, when the left endpoint \(l\) is fixed, extending the right endpoint \(r\) to the right (increasing it) causes the interval sum to monotonically increase. Using this monotonicity, the following property holds:

• For a left endpoint \(l\), let \(max\_r\) be the maximum right endpoint that satisfies the condition (interval sum \(\leq M\)).
• When the left endpoint advances to \(l+1\), the maximum right endpoint satisfying the condition is always at least \(max\_r\) (because moving the left endpoint to the right decreases or maintains the interval sum, potentially allowing the right endpoint to extend further).

Using this property, we can apply the Two Pointers technique, where the right pointer advances without ever moving backward.

Algorithm

To compute interval sums efficiently, we precompute a prefix sum array. Let the prefix sum array be \(S\), where \(S[i] = A_1 + A_2 + \cdots + A_i\) (\(S[0] = 0\)). The sum from day \(l\) to day \(r\) can be obtained in \(O(1)\) as \(S[r] - S[l-1]\).

The specific procedure is as follows (explained using 0-indexed notation):

1. Compute \(M = T / C\).
2. Build the prefix sum array \(S\) (\(S[i] = \sum_{j=0}^{i-1} A[j]\)).
3. Move the left endpoint \(i\) from \(0\) to \(N-K\) in order.
4. Start the right pointer \(R\) from the previous position (or \(i+K\), the minimum length requirement), and advance it to the right as long as \(S[R] - S[i] \leq M\) holds.
5. When the loop exits, \(R-1\) is the maximum right endpoint (\(max\_r\)) satisfying the condition.
6. If \(max\_r \geq i+K\), then the valid right endpoints for left endpoint \(i\) are all integers from \(i+K\) to \(max\_r\). Therefore, add the count \(max\_r - (i+K) + 1\) to the answer.

Complexity

• Time Complexity: \(O(N)\) Building the prefix sum takes \(O(N)\). In the two pointers part, both the left variable \(i\) and the right variable \(R\) monotonically increase from \(0\) to \(N\) without decreasing, so the inner while loop executes at most \(N\) times in total. Therefore, the overall time complexity is \(O(N)\), which runs sufficiently fast under the given constraints.

• Space Complexity: \(O(N)\) \(O(N)\) memory is used to store the input array \(A\) and the prefix sum array \(S\).

Implementation Notes

• Overflow Prevention: The answer (the number of valid pairs) can be as large as \(O(N^2)\) (up to approximately \(2 \times 10^{12}\)). This greatly exceeds the maximum value of a 32-bit integer type (C++ int, approximately \(2 \times 10^9\)), so the variable ans storing the answer must use a 64-bit integer type (C++ long long).

• Order of Division: If you compute \(C \times \text{interval sum} \leq T\) directly, there is a risk of overflow even with 64-bit integers because \(C\) and the interval sum can be large. By precomputing \(M = T / C\), you can safely avoid overflow.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long C, T, K;
    if (!(cin >> N >> C >> T >> K)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    long long M = T / C;

    vector<long long> S(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        S[i + 1] = S[i] + A[i];
    }

    long long ans = 0;
    long long R = 0;
    for (int i = 0; i <= N - K; ++i) {
        R = max(R, i + K);
        while (R <= N && S[R] - S[i] <= M) {
            R++;
        }
        long long max_r = R - 1;
        if (max_r >= i + K) {
            ans += max_r - (i + K) + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.