Summary

We simulate the process of infection spreading from residents whose immunity becomes \(0\) or less, and find the final number of infected people.

We manage the “earliest round” in which each resident gets infected using a priority queue, calculating the result without simulating the rounds one by one naively.

Analysis

First, let’s consider the number of attacks required for resident \(i\) with immunity \(H_i > 0\) to get infected.

Since the damage received per round from a single infected neighbor is \(D\), for resident \(i\) to get infected, it is sufficient to receive

\[ K_i = \left\lceil \frac{H_i}{D} \right\rceil \]

attacks.

For example, if \(H_i = 25\) and \(D = 10\), the immunity decreases by \(10\) each time, so the resident gets infected after receiving \(3\) attacks.

---

Here, we define the “infection time” as follows:

• The infection time of residents who are infected from the beginning is \(0\).
• The infection time of a resident who gets infected at the end of round \(t\) is \(t\).

A resident with infection time \(a\) starts attacking their neighbors from round \(a+1\).

Case 1: Getting infected from one neighbor

If a resident is only attacked by a single neighbor with infection time \(a\), it takes \(K\) rounds to receive \(K\) attacks, so the infection time is

\[ a + K \]

.

Case 2: Getting infected from two neighbors

Suppose the left and right neighbors get infected at infection times \(a\) and \(b\), respectively. Let \(a \leq b\).

The total number of attacks received by time \(T\) is

\[ (T-a) + \max(0, T-b) \]

.

• The left neighbor starts attacking from round \(a+1\), contributing \(T-a\) attacks.
• The right neighbor starts attacking from round \(b+1\), contributing \(T-b\) attacks.

If the resident gets infected by the first neighbor alone before the second neighbor even gets infected, we have

\[ a + K \leq b \]

so the infection time is

\[ a + K \]

.

Otherwise, there must be a period during which the resident is attacked by both neighbors simultaneously. In this case, we need to find the minimum \(T\) that satisfies

\[ (T-a) + (T-b) \geq K \]

so we have

\[ T = \left\lceil \frac{K+a+b}{2} \right\rceil \]

.

---

One important point to note is that in this problem, “if no new infected person appears in a round, the process terminates there.”

That is, even if some residents would eventually get infected if the rounds continued, they will not actually get infected if there is an empty round before that.

For example, even if a resident is scheduled to be infected at time \(2\), if nobody gets infected in round \(1\), that resident will not be infected.

Therefore, we process the infection times in ascending order and terminate the process if there is a gap between rounds.

Algorithm

We use a priority queue to process residents in ascending order of their scheduled infection times.

Variables to Manage

• K[i]
  • The number of attacks required for resident \(i\) to get infected. This is \(0\) for residents who are infected from the beginning as they don’t need it.
• best[i]
  • The earliest known infection time of resident \(i\) at the current moment.
• done[i]
  • Whether resident \(i\)’s infection has been finalized.
• cnt[i]
  • The number of infected neighbors of resident \(i\) found so far.
• first[i]
  • The infection time of the first infected neighbor found.
• heap
  • A priority queue containing pairs of (scheduled infection time, resident ID).
• last
  • The last round up to which infections have occurred continuously without interruption.

Steps

1. Push the residents who are infected from the beginning (i.e., \(H_i \leq 0\)) into the priority queue with infection time \(0\).
2. For other residents, precalculate \(K_i = \left\lceil \frac{H_i}{D} \right\rceil\).
3. Pop the resident with the minimum scheduled infection time from the priority queue.
4. If they are already processed or the information is outdated, ignore it.
5. If the scheduled infection time is greater than last + 1, there is a round with no new infections, so terminate the process.
6. Finalize the infection of this resident and increment the answer by \(1\).
7. Update the scheduled infection times of their left and right neighbors:
   • If this is the first infected neighbor found, the new time is \(t + K\).
   • If this is the second infected neighbor found, calculate the time using the formula described above.
8. Push the updated scheduled infection times into the priority queue.

Checking for Gaps Between Rounds

last represents “at least one person has been infected in each round up to this point.”

Initially, last = 0.

When the next popped infection time is \(t\):

• If \(t = last + 1\), infections continue in the next round, so we proceed (and update last = t).
• If \(t \leq last\), multiple people are just getting infected in the same round, so we proceed.
• If \(t > last + 1\), there is a round in between with no new infections, so we terminate.

Complexity

• Time Complexity: \(O(N \log N)\)
• Space Complexity: \(O(N)\)

Each resident’s infection is finalized at most once, and we only check their left and right neighbors.
Since push and pop operations on the priority queue take \(O(\log N)\) time, the overall time complexity is \(O(N \log N)\).

Implementation Details

In the calculation of infection times, pay attention to rounding up division.

\[ K_i = \left\lceil \frac{H_i}{D} \right\rceil \]

can be calculated in Python as:

K[i] = (H[i] + D - 1) // D

Also,

\[ \left\lceil \frac{K+a+b}{2} \right\rceil \]

can be calculated as:

(K + a + b + 1) // 2

Since outdated scheduled infection times may remain in the priority queue, when popping an element, we need to discard invalid information by doing:

if done[u] or t != best[u]:
    continue

Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N, D = data[0], data[1]
    INF = 10**30

    K = [0] * N
    best = [INF] * N
    done = [False] * N
    cnt = [0] * N
    first = [0] * N
    heap = []

    for i in range(N):
        h = data[2 + i]
        if h <= 0:
            best[i] = 0
            heap.append((0, i))
        else:
            K[i] = (h + D - 1) // D

    del data
    heapq.heapify(heap)

    heappush = heapq.heappush
    heappop = heapq.heappop

    ans = 0
    last = 0

    while heap:
        t, u = heappop(heap)
        if done[u] or t != best[u]:
            continue

        if t > 0 and t > last + 1:
            break

        done[u] = True
        ans += 1
        if t > 0 and t == last + 1:
            last = t

        if u > 0:
            v = u - 1
            if not done[v] and K[v]:
                k = K[v]
                c = cnt[v]
                if c == 0:
                    cnt[v] = 1
                    first[v] = t
                    cand = t + k
                else:
                    cnt[v] = 2
                    a = first[v]
                    if a + k <= t:
                        cand = a + k
                    else:
                        cand = (k + a + t + 1) // 2

                if cand < best[v]:
                    best[v] = cand
                    heappush(heap, (cand, v))

        if u + 1 < N:
            v = u + 1
            if not done[v] and K[v]:
                k = K[v]
                c = cnt[v]
                if c == 0:
                    cnt[v] = 1
                    first[v] = t
                    cand = t + k
                else:
                    cnt[v] = 2
                    a = first[v]
                    if a + k <= t:
                        cand = a + k
                    else:
                        cand = (k + a + t + 1) // 2

                if cand < best[v]:
                    best[v] = cand
                    heappush(heap, (cand, v))

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.