Volcanic Eruption
Source: codechef
Difficulty: 1793

Volcanic Eruption
There are$N$positions along a line, each of which contains either a building (with positive height) or a volcano.
You are given this information as an array$A$of length$N$, where$A_i = 0$represents a volcano at position$i$, and$A_i \gt 0$represents a building with height$A_i$at position$i$.
Initially, the lava level is$0$. Every second, all the volcanoes erupt simultaneously, increasing each of their lava levels by exactly$P$.
Lava behaves as follows:
Suppose the current lava level is$X$. Then, lava will flow left and and right from each volcano till it reaches a building whose height is
strictly greater
than$X$, at which point it will stop flowing.
For each$i$, determine the minimum time at which building$i$is completely submerged under lava.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of two lines of input.
The first line contains two space-separated integers$N$and$P$— the number of buildings and the rate at which lava level increases, respectively.
The second line contains$N$space-separated integers$A_1, A_2, \ldots, A_N$, describing information about the buildings and volcanoes as detailed in the statement.
Output Format
For each test case, output$N$space-separated integers, say$t_1, t_2, \ldots, t_N$.
If$A_i = 0$, then$t_i$should also be$0$.
If$A_i \gt 0$,$t_i$should be the minimum time at which building$i$is completely covered by lava.
Constraints$1 \leq T \leq 10^5$$1 \leq N \leq 3 \times 10^5$$1 \leq P \leq 10^9$$0 \leq A_i \leq 10^9$The sum of$N$across all test cases will not exceed$3 \times 10^5$.
There exists at least one index$i$such that$A_i = 0$.
Sample 1:
Explanation:
Test case$1$:
The lava behaves as follows:
In the first second, the lava level increases by$P = 2$and becomes$2$. No buildings are submerged.
In the next second, the lava level increases by$P = 2$and becomes$4$. The first building is now submerged since the lava from the volcano at index$2$will flow over it.
In the third second, the lava level increases by$2$again, and becomes$6$. The lava from the volcano at$2$moves right till it reaches index$5$; submerging buildings$3$and$4$.
In the fourth second, the lava level becomes$8$, and the final remaining building is submerged.
So, we obtain$t_1 = 2$,$t_3 = t_4 = 3$, and$t_5 = 4$.

Sample Input:
2
6 2
4 0 6 2 8 0
6 3
4 0 6 2 8 0

Sample Output:
2 0 3 3 4 0 
2 0 2 2 3 0

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

#define Alhamdulillah ios_base::sync_with_stdio(0), cin.tie(0);
#define ll long long
#define endl '\n'
#define db(i) cout << "c -> " << i << endl;
#define pv(v) for(auto e : v)   cout << e << " ";   cout << endl;
#define pm(m) for(auto [x,y] : m)   cout << x << " " << y << endl;   cout << endl;

const int N = 3e5+9;
int a[N];
int psum[N], ssum[N] ;

void solve(){
    int n,p,mx,z; cin >> n >> p;

    //left->right
    mx = 0LL, z = 0LL;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        if(a[i] == 0)  psum[i] = 0, mx = 0, ++z;
        else if(!z) psum[i] = INT_MAX;
        else if(a[i] <= mx) psum[i] = (mx+p-1)/p;
        else if(a[i] > mx){
            mx = a[i];
            psum[i] = (mx+p-1)/p; 
        }
    }

    //right->left
    mx = 0LL, z = 0LL;
    for(int i=n;i>=1;i--){
        if(a[i] == 0)  ssum[i] = 0, mx = 0, z++;
        else if(!z) ssum[i] = INT_MAX;
        else if(a[i] <= mx) ssum[i] = (mx+p-1)/p;
        else if(a[i] > mx){
            mx = a[i];
            ssum[i] = (mx+p-1)/p; 
        }
    }

    // for(int i=1;i<=n;i++)   cout << psum[i] << " "; 
    // cout << endl;
    // for(int i=1;i<=n;i++)   cout << ssum[i] << " ";
    // cout << endl;
    for(int i=1;i<=n;i++)   cout << min(psum[i], ssum[i]) << " ";
    cout << endl;
}

int main(){
    Alhamdulillah
    int t=1;    cin >> t;
    while(t--)  solve();
    return 0;
}

Go solution:
package main

import (
    "fmt"
    "math"
    "os"
    "strconv"
    "strings"
)

func precomputeLogTable(maxN int) []int {
    logTable := make([]int, maxN+1)
    for i := 2; i <= maxN; i++ {
        logTable[i] = logTable[i/2] + 1
    }
    return logTable
}

func main() {
    const maxN = 3 * 100000 + 1
    logTable := precomputeLogTable(maxN)

    input, _ := os.ReadFile("/dev/stdin")
    data := strings.Fields(string(input))
    index := 0
    T, _ := strconv.Atoi(data[index])
    index++

    for t := 0; t < T; t++ {
        N, _ := strconv.Atoi(data[index])
        P, _ := strconv.Atoi(data[index+1])
        index += 2

        A := make([]int, N)
        for i := 0; i < N; i++ {
            A[i], _ = strconv.Atoi(data[index+i])
        }
        index += N

        leftVolcano := make([]int, N)
        lastV := -1
        for i := 0; i < N; i++ {
            if A[i] == 0 {
                lastV = i
            }
            leftVolcano[i] = lastV
        }

        rightVolcano := make([]int, N)
        lastV = N
        for i := N - 1; i >= 0; i-- {
            if A[i] == 0 {
                lastV = i
            }
            rightVolcano[i] = lastV
        }

        kMax := logTable[N] + 1
        st := make([][]int, kMax)
        st[0] = make([]int, N)
        copy(st[0], A)

        currentK := 1
        for (1 << currentK) <= N {
            prevK := currentK - 1
            step := 1 << prevK
            newRow := make([]int, N)
            for i := 0; i <= N-(1<<currentK); i++ {
                newRow[i] = int(math.Max(float64(st[prevK][i]), float64(st[prevK][i+step])))
            }
            st[currentK] = newRow
            currentK++
        }

        getMax := func(l int, r int) int {
            if l > r {
                return 0
            }
            length := r - l + 1
            k := logTable[length]
            return int(math.Max(float64(st[k][l]), float64(st[k][r-(1<<k)+1])))
        }

        result := make([]int, N)
        for i := 0; i < N; i++ {
            if A[i] == 0 {
                result[i] = 0
                continue
            }

            var possibleX []int
            lv := leftVolcano[i]
            if lv != -1 {
                leftMax := getMax(lv+1, i-1)
                possibleX = append(possibleX, int(math.Max(float64(A[i]), float64(leftMax))))
            }
            rv := rightVolcano[i]
            if rv != N {
                rightMax := getMax(i+1, rv-1)
                possibleX = append(possibleX, int(math.Max(float64(A[i]), float64(rightMax))))
            }

            X := math.MaxInt32
            for _, val := range possibleX {
                if val < X {
                    X = val
                }
            }
            
            result[i] = int(math.Ceil(float64(X) / float64(P)))
        }
        
        fmt.Println(strings.Trim(fmt.Sprint(result), "[]"))
    }
}

Java solution:
import java.io.*;
import java.util.*;
public class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        
        
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    private static long[] processLeftToRight(long[] heights, long power, int size) {
        long[] timeNeeded = new long[size];
        Arrays.fill(timeNeeded, Long.MAX_VALUE);
        
        long lastVolcanoPos = -1;
        long currentMaxHeight = 0;
        
        for (int i = 0; i < size; i++) {
            if (heights[i] == 0) {
                lastVolcanoPos = i;
                timeNeeded[i] = 0;
                currentMaxHeight = 0;
            } else if (lastVolcanoPos != -1) {
                currentMaxHeight = Math.max(currentMaxHeight, heights[i]);
                long timeCandidate = calculateTimeNeeded(currentMaxHeight, power);
                timeNeeded[i] = Math.min(timeNeeded[i], timeCandidate);
            }
        }
        return timeNeeded;
    }

    private static long[] processRightToLeft(long[] heights, long[] currentTimes, long power, int size) {
        long lastVolcanoPos = -1;
        long currentMaxHeight = 0;
        
        for (int i = size - 1; i >= 0; i--) {
            if (heights[i] == 0) {
                lastVolcanoPos = i;
                currentTimes[i] = 0;
                currentMaxHeight = 0;
            } else if (lastVolcanoPos != -1) {
                currentMaxHeight = Math.max(currentMaxHeight, heights[i]);
                long timeCandidate = calculateTimeNeeded(currentMaxHeight, power);
                currentTimes[i] = Math.min(currentTimes[i], timeCandidate);
            }
        }
        return currentTimes;
    }

    private static long calculateTimeNeeded(long height, long power) {
        return (height + power - 1) / power;
    }

    private static void printResult(long[] heights, long[] times, int size) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < size; i++) {
            if (heights[i] == 0) {
                result.append("0 ");
            } else {
                result.append(times[i]).append(" ");
            }
        }
        result.append("\n");
        System.out.print(result.toString());
    }

    public static void main(String[] args) {
        FastReader fr = new FastReader();
        int testCases = fr.nextInt();
        
        while (testCases-- > 0) {
            int size = fr.nextInt();
            long power = fr.nextLong();
            
            long[] heights = new long[size];
            for (int i = 0; i < size; i++) {
                heights[i] = fr.nextLong();
            }
            
            long[] times = processLeftToRight(heights, power, size);
            
            times = processRightToLeft(heights, times, power, size);
            
            printResult(heights, times, size);
        }
    }
}

JavaScript solution:
function ceilingDivision(a, b) {
    return Math.ceil(a / b);
}

function solve() {
    const input = require('fs').readFileSync(0, 'utf-8').split("\n");
    let idx = 0;
    let T = parseInt(input[idx++]);

    while (T--) {
        const [N, P] = input[idx++].split(" ").map(Number);
        const A = input[idx++].split(" ").map(Number);

        const INF = Number.MAX_SAFE_INTEGER;
        const t_i = new Array(N).fill(INF);
        const heap = [];

        // Initialize the heap with volcano positions (where A[i] == 0)
        for (let i = 0; i < N; i++) {
            if (A[i] === 0) {
                t_i[i] = 0;
                heap.push(i);
            }
        }

        const directions = [-1, 1];

        // Process the heap in a manner similar to Dijkstra's algorithm
        while (heap.length > 0) {
            const u = heap.pop(); // Get the last element
            const current_t = t_i[u];

            for (let d = 0; d < directions.length; d++) {
                const v = u + directions[d];
                if (v < 0 || v >= N) continue;

                const required_t = (A[v] === 0) ? 0 : ceilingDivision(A[v], P);
                const new_t = Math.max(current_t, required_t);

                if (new_t < t_i[v]) {
                    t_i[v] = new_t;
                    heap.push(v);
                }
            }
        }

        // Output the result
        let result = '';
        for (let i = 0; i < N; i++) {
            result += (A[i] === 0 ? '0 ' : t_i[i] + ' ');
        }
        console.log(result.trim());
    }
}

solve();

Python solution:
def prog():
    t = int(input())
    for i in range(t):
        st = input().split()
        N = int(st[0])
        P = int(st[1])
        st = input().split()
        A = []
        V = []
        P1 = P-1
        for k in range(N):
            n = int(st[k])
            if n == 0:
                A.append(0)
                V.append(k)
            else:
                A.append((n+P1)//P)
            # endif
        # endfor k
        p = V[0]
        if p > 0:
            p -= 1
            while p > 0:
                if A[p] > A[p-1]:
                    A[p-1] = A[p]
                # endif
                p -= 1
            # endwhile
        # endif
        p = V[-1]
        if p < N-1:
            p += 1
            while p < N-1:
                if A[p] > A[p+1]:
                    A[p+1] = A[p]
                # endif
                p += 1
            # endwhile
        # endif
        sz = len(V)
        for k in range(sz-1):
            p = V[k] +1
            q = V[k+1] -1
            while q-p > 1:
                if A[p] < A[q]:
                    p += 1
                    if A[p-1] > A[p]:
                        A[p] = A[p-1]
                    # endif
                else:
                    q -= 1
                    if A[q+1] > A[q]:
                        A[q] = A[q+1]
                    # endif
                # endif
            # endwhile
        # endfor k
        for n in A:
            print (n, end=' ')
        # endfor n
        print()
    # endfor i
# end fun
prog()

Ruby solution:
def solve
  input = $stdin.read.split
  ptr = 0
  test_cases = input[ptr].to_i
  ptr += 1
  results = []
  
  test_cases.times do
    n = input[ptr].to_i
    p = input[ptr + 1].to_i
    ptr += 2
    a = input[ptr, n].map(&:to_i)
    ptr += n
    
    left_time = Array.new(n, Float::INFINITY)
    right_time = Array.new(n, Float::INFINITY)
    
    # Process left to right
    last_volcano = nil
    current_time = 0
    current_level = 0
    
    (0...n).each do |i|
      if a[i] == 0
        last_volcano = i
        current_time = 0
        current_level = 0
      else
        if last_volcano != nil
          if a[i] > current_level
            delta = a[i] - current_level
            steps = (delta + p - 1) / p  # Equivalent to ceil(delta / p)
            current_time += steps
            current_level += steps * p
          end
          left_time[i] = current_time
        end
      end
    end
    
    # Process right to left
    last_volcano = nil
    current_time = 0
    current_level = 0
    
    (n - 1).downto(0) do |i|
      if a[i] == 0
        last_volcano = i
        current_time = 0
        current_level = 0
      else
        if last_volcano != nil
          if a[i] > current_level
            delta = a[i] - current_level
            steps = (delta + p - 1) / p
            current_time += steps
            current_level += steps * p
          end
          right_time[i] = current_time
        end
      end
    end
    
    res = []
    (0...n).each do |i|
      if a[i] == 0
        res << 0
      else
        min_time = [left_time[i], right_time[i]].min
        res << min_time
      end
    end
    
    results << res.join(' ')
  end
  
  puts results.join("\n")
end

solve