Levels cleared from every starting point

Restate the rule with prefix sums. Let P[t] = layers[0] + ... + layers[t-1]. Starting at i with K energy, after paying for level j you hold K - (P[j+1] - P[i]). You pass level j when that is at least energy[j]:

K - P[j+1] + P[i] >= energy[j]
<=>  P[j+1] + energy[j] <= K + P[i]

So define one number per level, need[j] = P[j+1] + energy[j], and one threshold per start, T[i] = K + P[i]. The score from i is the length of the run of levels j = i, i+1, ... with need[j] <= T[i]. In other words, answer[i] = stop(i) - i, where stop(i) is the first j >= i with need[j] > T[i] (or n if none).

Brute force (say it first). Simulate from every start: O(n^2). Fine for n up to a few thousand, and a good oracle for testing.

Optimal: two pointers, O(n). With non-negative costs, P is non-decreasing, so T[i] is non-decreasing in i. That makes stop(i) monotone:

• Every j in [i+1, stop(i)) had need[j] <= T[i] <= T[i+1], so the run from i+1 reaches at least stop(i).
• Therefore stop(i+1) >= max(stop(i), i+1).

Keep one pointer j that only moves forward. For each i, first set j = max(j, i), then advance while j < n and need[j] <= T[i]. The pointer moves at most n times in total.

Invariant: at the start of iteration i, every level in [i, j) satisfies need <= T[i]. It holds because those levels passed an earlier, smaller-or-equal threshold.

If costs can be negative the monotonicity breaks. Then use a sparse table (or segment tree) of range max over need and binary search, per start, for the first index whose prefix max exceeds T[i]: O(n log n). The code includes that version too.

from typing import List


def max_levels_brute(layers: List[int], energy: List[int], k: int) -> List[int]:
    """O(n^2) simulation. Used as a test oracle."""
    n = len(layers)
    out = []
    for i in range(n):
        cur, score = k, 0
        for j in range(i, n):
            cur -= layers[j]
            if cur < energy[j]:
                break
            score += 1
        out.append(score)
    return out


def max_levels(layers: List[int], energy: List[int], k: int) -> List[int]:
    """O(n) two pointers. Requires layers[j] >= 0."""
    n = len(layers)
    prefix = [0] * (n + 1)
    for t, cost in enumerate(layers):
        prefix[t + 1] = prefix[t] + cost
    need = [prefix[j + 1] + energy[j] for j in range(n)]

    out = [0] * n
    j = 0
    for i in range(n):
        j = max(j, i)
        threshold = k + prefix[i]
        while j < n and need[j] <= threshold:
            j += 1
        out[i] = j - i
    return out


def max_levels_any_sign(layers: List[int], energy: List[int], k: int) -> List[int]:
    """O(n log n) sparse table + binary lifting. Works with negative costs."""
    n = len(layers)
    if n == 0:
        return []
    prefix = [0] * (n + 1)
    for t, cost in enumerate(layers):
        prefix[t + 1] = prefix[t] + cost
    need = [prefix[j + 1] + energy[j] for j in range(n)]

    # table[p][x] = max(need[x : x + 2**p])
    table = [need[:]]
    p = 1
    while (1 << p) <= n:
        prev, half = table[-1], 1 << (p - 1)
        table.append([max(prev[x], prev[x + half])
                      for x in range(n - (1 << p) + 1)])
        p += 1

    out = [0] * n
    for i in range(n):
        threshold = k + prefix[i]
        pos = i  # levels [i, pos) all pass
        for q in range(len(table) - 1, -1, -1):
            if pos + (1 << q) <= n and table[q][pos] <= threshold:
                pos += 1 << q
        out[i] = pos - i
    return out


if __name__ == "__main__":
    import random

    assert max_levels([2, 3, 1, 4], [5, 2, 4, 1], 10) == [3, 3, 2, 1]
    assert max_levels([1, 1, 1], [0, 0, 0], 3) == [3, 2, 1]
    assert max_levels([5], [0], 4) == [0]
    assert max_levels([], [], 7) == []
    for _ in range(2000):
        n = random.randint(0, 12)
        lay = [random.randint(0, 6) for _ in range(n)]
        en = [random.randint(0, 8) for _ in range(n)]
        kk = random.randint(0, 25)
        want = max_levels_brute(lay, en, kk)
        assert max_levels(lay, en, kk) == want
        assert max_levels_any_sign(lay, en, kk) == want
        neg = [random.randint(-4, 6) for _ in range(n)]
        assert max_levels_any_sign(neg, en, kk) == max_levels_brute(neg, en, kk)
    print("ok")

• Brute force: O(n^2) time, O(1) extra space.
• Two pointers: O(n) time (each pointer moves at most n steps), O(n) space for prefix, need and the output.
• Sparse table (negative costs allowed): O(n log n) to build, O(log n) per start, O(n log n) space.

• layers=[2,3,1,4], energy=[5,2,4,1], K=10 -> [3,3,2,1]. From 0: 8>=5, 5>=2, 4>=4, then 0<1, so 3. From 1: 7>=2, 6>=4, 2>=1, so 3.
• layers=[1,1,1], energy=[0,0,0], K=3 -> [3,2,1] (energy reaches exactly 0 and still passes, since the test is >=).
• layers=[5], energy=[0], K=4 -> [0] (remaining energy is negative).
• Empty arrays -> [].
• layers=[0,0], energy=[10,0], K=5 -> [0,1] (a hard first level blocks start 0 but not start 1).
• All levels free and requirements 0 -> [n, n-1, ..., 1].
• Large K (bigger than total cost plus any requirement) -> every start clears to the end.
• Randomized cross-check against the brute force, as in the code.

1. Negative costs (levels that refill energy). T[i] is no longer monotone, so two pointers fail. Use the sparse table plus binary lifting (shown), or a segment tree with "first index > x at or after i" descent. O(n log n).
2. Online queries (i, K_q) with different starting energy. Thresholds are now arbitrary, so precompute the sparse table once and answer each query in O(log n). If queries can be sorted offline by K_q + P[i], a monotonic stack of "next greater need" also works.
3. Skip one failed level per run (one life). Track two states per start: the stop point with no skip, then restart the scan from stop(i) + 1 with the energy after paying for the skipped level (or not paying, depending on the rule). Range-max search still makes each step O(log n).
4. Point updates to layers or energy. A cost change shifts every later need and every later threshold by the same amount. Store need in a segment tree with lazy range add, and keep P in a Fenwick tree. Each query becomes a tree descent, O(log n).
5. Best start only (max of the answer array). Same O(n) pass and take the max. With a fixed run length L, a sliding window check also works.

Mid-level (L4)

• Gets the simulation right, including the >= comparison and that each run starts fresh with K.
• States O(n^2) and recognizes it is too slow for n around 1e5.
• Reaches prefix sums and a correct faster method with some hints.

Senior (L5)

• Rewrites the pass condition as need[j] <= K + P[i] without help.
• Proves the stop index is monotone and writes the O(n) two-pointer solution cleanly.
• Tests edge cases: empty input, exact-zero remaining energy, a failing first level, very large K.

Staff (L6+)

• Names the assumption behind the monotone argument (non-negative costs) and gives the O(n log n) fix when it fails.
• Handles per-query starting energy and updates with a segment tree, and explains the tradeoffs.
• Uses a brute-force oracle with randomized tests to back up the optimized code.