Problem Analysis

The problem requires finding, for each position i in an array, the maximum value k such that the sum of elements in the left interval [i, i+k-1] and the sum of elements in the right interval [i+k, i+2*k-1] are both less than or equal to a given value s.

Why Binary Search Fails

At first glance, one might consider using binary search to solve this problem. However, the solution does not satisfy the monotonicity required for binary search. As k increases, the sum of the left interval does increase monotonically, but the sum of the right interval can either increase or decrease, violating the monotonicity condition.

Consider the following example:

6 10
1 6 3 8 1 1

When i=1 and k=2, the right interval sum exceeds s, but when k=3, both interval sums satisfy the condition.

Two-Pointer Approach

A brute-force approach would check all possible k values for each i, resulting in O(n^2) time complexity, which is too slow for n ≤ 10^5. Instead, we can solve the problem in O(n) time by processing the array from right to left and leveraging the fact that the right boundary of the left interval is monotonically non-increasing.

Algorithm Correctness

Let r be the right boundary of the left interval. We can prove that as we move from i to i-1, the right boundary r is monotonically non-increasing:

• Initialization: When i=n, the optimal k is 0.
• Maintenance: When moving from i+1 to i, there are two cases:
  • If the interval [i, r] still satisfies the conditions, r remains the same or decreases due to the constraint r+k ≤ n.
  • If the interval [i, r] no longer satisfies the conditions, we decrease r until the conditions are met again.
• Termination: The process terminates when i=1.

Implementation

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 100005;

int main() {
    int n, s;
    cin >> n >> s;
    
    vector<int> arr(n+1);
    vector<long long> prefix_sum(n+1, 0);
    vector<int> result(n+1);
    
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        prefix_sum[i] = prefix_sum[i-1] + arr[i];
    }
    
    int right_bound = n;
    for (int i = n; i >= 1; i--) {
        while (right_bound >= i) {
            int k = right_bound - i + 1;
            if (right_bound + k <= n && 
                prefix_sum[right_bound] - prefix_sum[i-1] <= s && 
                prefix_sum[right_bound + k] - prefix_sum[right_bound] <= s) {
                break;
            }
            right_bound--;
        }
        result[i] = 2 * (right_bound - i + 1);
    }
    
    for (int i = 1; i <= n; i++) {
        cout << result[i] << endl;
    }
    
    return 0;
}

Complexity Analysis

The algorithm processes each element once, and the right_bound pointer only moves leftward, resulting in O(n) time complexity. The space complexity is O(n) for storing the prefix sums and results.