Overview

For each section, consider the amount that needs to be increased from the current value \(A_i\) to the target value \(B_i\).
Determine whether it is possible to make all sections exactly reach their target values using only interval addition operations of length \(K\), and if so, find the minimum number of operations.

Analysis

Let the required increase for section \(i\) be

\[ D_i = B_i - A_i \]

Since operations can only increase the water amount, each section must ultimately receive exactly \(D_i\) additions.

The key insight is that when scanning from left to right, the number of operations that must start at each position is uniquely determined.

For example, consider section \(i\):

• Due to operations already started to the left, section \(i\) has already received cur additions
• To reach the target for section \(i\), a total of \(D_i\) additions are needed
• Operations starting to the right in the future will not affect section \(i\)

Therefore, if an operation can be started at section \(i\), the number of operations starting at section \(i\) must be

\[ D_i - cur \]

If this value is negative, too many additions have already been made, so it is impossible.

Also, operations can only start at positions from \(1\) to \(N-K+1\).
Therefore, at positions \(i > N-K+1\), no new operations can be started.
In this case, the existing accumulated addition cur must exactly match \(D_i\), otherwise it is impossible.

Why a naive approach is too slow

If we perform need operations at section \(i\) and actually update each element in the interval \([i, i+K-1]\) every time, the worst case is

\[ O(NK) \]

or even more when the number of operations is large.

Since \(N\) can be up to \(3 \times 10^5\), this is too slow.

Therefore, to efficiently manage interval additions, we use the idea of the imos method (difference array technique).

Algorithm

We scan sections from left to right.

We maintain the following variables:

• cur: the accumulated addition amount applied to the current section by previous operations
• diff: the difference array for the imos method
• ans: the total number of operations
• lastStart = N - K + 1: the last position where an operation can start

When we arrive at section \(i\), first we do

cur += diff[i];

to reflect the addition amount entering section \(i\).

Next, let the required increase for section \(i\) be

\[ target = B_i - A_i \]

Case: \(i \leq lastStart\)

An operation can be started at this position.

To make section \(i\) exactly reach its target value, we need to start

\[ need = target - cur \]

operations from section \(i\).

• If need < 0, too many additions have already been made, so it is impossible
• Otherwise, perform need operations

Starting need operations adds need to the interval \([i, i+K-1]\).

Therefore, we do

cur += need;
diff[i + K] -= need;

so that the effect expires at the position right after the end of the interval.

Then we add to the operation count:

ans += need;

Case: \(i > lastStart\)

No new operations can be started from this position.

Therefore, the already accumulated addition cur must exactly equal target.

if (cur != target) {
    // Impossible
}

If all sections are verified without issues, ans is the answer.

Concrete Example

For example, with \(N=5, K=3\), suppose the required increases are

\[ D = [1, 2, 2, 1, 0] \]

• At section \(1\), the accumulated addition is \(0\)
  The required amount is \(1\), so we perform \(1\) operation starting at position \(1\)
• At section \(2\), already \(1\) has been added
  The required amount is \(2\), so we perform \(1\) operation starting at position \(2\)
• At section \(3\), already \(2\) has been added
  The required amount is also \(2\), so no new operation is needed
• At sections \(4, 5\), no new operations can be started, so we only check whether the current accumulated addition matches the required amount

In this way, by scanning from left to right, the number of operations to perform at each position is determined.

Complexity

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

Implementation Notes

• The total number of operations can be large, so use long long.
• diff[i + K] -= need ensures that the effect of the interval addition disappears from position \(i+K\) onward.
• Using \(1\)-indexed arrays makes it easier to handle the interval \([i, i+K-1]\).
• The last position where an operation can start is

\[ N - K + 1 \]

Note that no new operations can be started to the right of this position.

Source Code

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

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

    int N, K;
    cin >> N >> K;

    vector<long long> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) cin >> B[i];

    vector<long long> diff(N + 2, 0);

    long long cur = 0;
    long long ans = 0;
    int lastStart = N - K + 1;

    for (int i = 1; i <= N; i++) {
        cur += diff[i];

        long long target = B[i] - A[i];

        if (i <= lastStart) {
            long long need = target - cur;
            if (need < 0) {
                cout << -1 << '\n';
                return 0;
            }

            ans += need;
            cur += need;

            if (i + K <= N + 1) {
                diff[i + K] -= need;
            }
        } else {
            if (cur != target) {
                cout << -1 << '\n';
                return 0;
            }
        }
    }

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

---

This editorial was generated by gpt-5.5-high.