Overview

Determine whether it is possible to transform array \(A\) into exactly array \(B\) using operations that add \(1\) to a contiguous segment of length \(K\).
If possible, find the minimum number of operations required.

Analysis

For each section \(i\), define the required increase as

\[ D_i = B_i - A_i \]

Since operations can only increase values, each section \(i\) must ultimately have exactly \(D_i\) added to it.

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

For example, consider section \(i\).
The operations that can affect section \(i\) are those with starting positions from \(i-K+1\) to \(i\).

When processing from left to right, let cur be the total amount already added to section \(i\) by previously started operations.

If we can start a new operation from section \(i\), then the number of operations needed to match the target for section \(i\) is

\[ D_i - cur \]

• If \(D_i - cur < 0\):
  The target has already been exceeded, so it is impossible.
• If \(D_i - cur \geq 0\):
  We have no choice but to start exactly that many operations from section \(i\).

The reason it is “no choice” is that operations starting further to the right cannot affect section \(i\).
In other words, starting an operation from section \(i\) is the last chance to bring section \(i\) to exactly its target value.

On the other hand, at positions near the right end, it is no longer possible to start a new segment of length \(K\).
In that case, we simply check whether the accumulated amount cur from already performed operations matches \(D_i\).

Naively simulating operations one at a time would not be fast enough, as the answer can be up to approximately \(3 \times 10^{14}\).
Also, updating the entire segment of length \(K\) for each operation would result in \(O(NK)\), which is too slow for \(N \leq 3 \times 10^5\).

Therefore, we manage the total number of operations affecting the current position as cur, allowing each section to be processed in \(O(1)\).

Algorithm

We use \(0\)-indexed notation.

Since operations can start at positions \(0\) through \(N-K\), we define the count of such positions as

\[ M = N - K + 1 \]

Let used[i] be “the number of operations started at position \(i\).”
Also, let cur be “the total amount added to the current section by already started operations.”

We process \(i = 0, 1, \ldots, N-1\) from left to right.

1. When arriving at position \(i\), the operation started \(K\) positions ago no longer has an effect, so subtract it from cur if necessary:

$\( \text{If } i \geq K, \text{ then } cur \mathrel{-}= used[i-K] \)$

1. Compute the required increase:

$\( d = B_i - A_i \)$

1. If we can still start an operation from position \(i\), i.e., \(i < M\):

Since cur has already been added, the additional number of operations needed is

$\( add = d - cur \)$

• If add < 0, it is impossible.
• Otherwise, start add operations from position \(i\).

Therefore:

   used[i] = add
   cur += add
   ans += add

1. If we can no longer start an operation, i.e., \(i \geq M\):

Since no new adjustments can be made,

$\( cur = d \)$

must hold; otherwise it is impossible.

If the entire process completes without contradiction, ans is the answer.

Example

For example, suppose \(K=3\) and the required increases are

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

Processing from left to right:

• At position \(1\): cur = 0, so start \(1\) operation
• At position \(2\): cur = 1, so start \(1\) more operation
• At position \(3\): cur = 2, so no additional operations needed
• At position \(4\) and beyond: no new operations can be started, so just check whether cur matches the target

In this way, the number of operations to start at each position is uniquely determined from left to right.

Complexity

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

Implementation Notes

• cur is the total number of operations affecting the current position.

• When arriving at position \(i\), the operation started at \(i-K\) is now out of range, so it is subtracted from cur.

• The answer may not fit in a \(32\)-bit integer, so in C++ you need to use long long. In Python, integers have arbitrary precision, so there is no issue.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    M = N - K + 1
    used = [0] * M

    cur = 0
    ans = 0

    for i in range(N):
        if i >= K:
            cur -= used[i - K]

        d = B[i] - A[i]

        if i < M:
            add = d - cur
            if add < 0:
                print(-1)
                return
            used[i] = add
            cur += add
            ans += add
        else:
            if cur != d:
                print(-1)
                return

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.