Levels cleared from every starting point

A game has n levels in a row. You are given two integer arrays of length n, layers and energy, and an integer K.

A run that starts at level i begins with exactly K energy and plays levels i, i+1, i+2, ... in order. At level j:

1. Pay layers[j] energy.
2. If the energy you have left is at least energy[j], you clear the level, score 1 point, and move on to j+1.
3. Otherwise the run ends at once. No later level counts.

Every run is independent and starts again with K energy.

Return an array answer of length n where answer[i] is the score of the run that starts at level i.

Implement:

def max_levels(layers: list[int], energy: list[int], k: int) -> list[int]: ...

Constraints

• 1 <= n <= 10^5
• 0 <= layers[j], energy[j] <= 10^9
• 0 <= K <= 10^14

Example 1

layers = [2, 3, 1, 4], energy = [5, 2, 4, 1], K = 10
output = [3, 3, 2, 1]

From level 0: 10-2=8 (>=5, pass), 8-3=5 (>=2, pass), 5-1=4 (>=4, pass), 4-4=0 (<1, stop). Score 3.
From level 1: 7 (>=2), 6 (>=4), 2 (>=1). Score 3.

Example 2

layers = [0, 0], energy = [10, 0], K = 5
output = [0, 1]

Level 0 needs 10 energy left, so a run from 0 scores nothing. A run from 1 clears level 1.

An O(n^2) simulation is a fine start. Aim for O(n) or O(n log n).