3964. Minimum Lights to Illuminate a Road

You are given an integer array lights of length n, representing positions 0 through n - 1 on a road.

For each position i:

• If lights[i] = v, where v > 0, there is a working bulb at position i that illuminates every position from max(0, i - v) to min(n - 1, i + v), inclusive.
• If lights[i] = 0, there is no working bulb at position i.

A position is visible if it is illuminated by at least one working bulb.

You may install additional bulbs at any positions. Each additional bulb installed at position j illuminates positions from max(0, j - 1) to min(n - 1, j + 1), inclusive.

Return the minimum number of additional bulbs required to make every position on the road visible.

class Solution {
public:
    int minLights(vector<int>& lights) {
        int n = lights.size(), res = 0;
        vector<bool> on(lights.size());
        for(int i = 0, until = -1; i < n; i++) {
            if(lights[i]) until = max(until, i + lights[i]);
            if(until >= i) on[i] = 1;
        }
        for(int i = n - 1, until = n; i >= 0; i--) {
            if(lights[i]) until = min(until, i - lights[i]);
            if(until <= i) on[i] = 1;
        }
        auto ok = [&](int x) {
            return 0 <= x and x < n;
        };
        auto up = [&](int x) {
            for(auto& p : {-1,0,1}) if(ok(x+p)) on[x+p] = 1;
        };
        for(int i = 0; i < n; i++) {
            if(on[i]) continue;
            if(i == n - 1) up(i);
            else up(i+1);
            res++;
        }
        return res;
    }
};