Overview

When infected individuals deal \(D\) damage to their neighbors each round, we want to find the number of people who will be infected before the spread stops.

We convert each person’s immunity into “how many attacks they need to receive to become infected”, and process the infection times in ascending order using a priority queue.

Analysis

When resident \(i\) has immunity \(H_i > 0\), the number of attacks required for this resident to become infected is:

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

For example, if \(H_i = 10\) and \(D = 3\), \(3\) attacks only reduce the immunity by \(9\), so \(4\) attacks are required.

---

A naive round-by-round simulation can take up to \(10^9\) rounds until infection, depending on the values of \(H_i\) and \(D\).

Although \(N\) is \(2 \times 10^5\), since the number of rounds can be extremely large, a simple simulation will not run in time.

Therefore, we only process events of “who will be infected next, and in which round”.

---

If we know the infection times of the left and right neighbors of resident \(i\), we can calculate the earliest infection time for resident \(i\).

Let the infection time be defined as “the round at the end of which the person becomes infected”. The infection time of the initially infected individuals is \(0\).

When only one neighbor is infected

Suppose a neighbor is infected at time \(a\).

That neighbor starts attacking from round \(a+1\).

Since resident \(i\) only needs to receive \(K_i\) attacks to be infected, the infection time is:

\[ a + K_i \]

When both neighbors are infected

Let the infection times of the left and right neighbors be \(a\) and \(b\), and assume \(a \leq b\).

Until time \(b\), only the neighbor who was infected first will attack.

The number of attacks received during this period is:

\[ b - a \]

If

\[ K_i \leq b - a \]

then they will be infected by the attacks from just one side, so the infection time is:

\[ a + K_i \]

Otherwise, from time \(b\) onwards, they will receive a total of \(2\) attacks per round from both neighbors.

Since the number of attacks received by time \(t\) is

\[ (b-a) + 2(t-b) \]

the minimum \(t\) for which this value is at least \(K_i\) is:

\[ t = \left\lceil \frac{K_i + a + b}{2} \right\rceil \]

---

Also, in this problem, the condition “if no new infections occur in a certain round, the process terminates” is crucial.

That is, even if someone is theoretically infected in round \(10\), if there are no new infections in round \(3\), the process terminates there, and round \(10\) is never reached.

Therefore, while processing infection events in chronological order, we check:

• Whether there are infected individuals in round 1
• Whether there are infected individuals in round 2
• Whether there are infected individuals in round 3

and so on, in order.

If the next infection time is strictly later than the currently required round, the propagation stops there.

Algorithm

For each resident, we maintain the following:

• infected[i]: whether they are already infected
• left_time[i]: the time when their left neighbor was infected
• right_time[i]: the time when their right neighbor was infected
• cand[i]: the currently known earliest infection time for resident \(i\)

Candidate infections are managed using a priority queue, and we retrieve them in ascending order of infection time.

---

The procedure is as follows:

1. For each resident, if \(H_i \leq 0\), they are initially infected.
2. For residents with \(H_i > 0\), calculate the required number of attacks:

$\( K_i = \left\lceil \frac{H_i}{D} \right\rceil \)$

1. For the neighbors of the initially infected individuals, record the infected neighbor’s time as \(0\), calculate the candidate infection time, and insert it into the priority queue.
2. Set expected = 1. This represents “the next round in which a new infection must occur”.
3. Retrieve the minimum infection time \(t\) from the priority queue.
   • If the queue is empty, terminate.
   • If \(t > expected\), terminate because there are no new infections in round expected.
4. Mark all residents who get infected at time \(t\) as infected at once.
5. For the neighbors of newly infected residents, recalculate their candidate infection times and add them to the priority queue if necessary.
6. If \(t = expected\), increment expected by \(1\) to check the next round.
7. Go back to step 5.

---

Since multiple people can be infected at the same time, we process candidates with the same infection time \(t\) together.

This corresponds to the problem statement’s condition that “infections occur simultaneously at the end of a round”.

Complexity

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

Each resident is infected at most once, and updating candidate times for neighbors happens at most a constant number of times. Since inserting into and retrieving from the priority queue takes \(O(\log N)\), the overall complexity is \(O(N \log N)\).

Implementation Details

Old candidates may remain in the priority queue.

For example, after calculating a candidate time when only one neighbor is infected, the other neighbor might also get infected later, leading to an earlier candidate infection time.

Therefore, when retrieving from the queue, we check:

if (infected[i] || cand[i] != t)

to discard elements that are already infected or are outdated candidates.

Also, since \(H_i\) and \(D\) can be up to \(10^9\) and the infection times can become very large, it is necessary to use long long (or 64-bit integers) for the calculations.

Source Code

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

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll D;
    cin >> N >> D;

    vector<ll> H(N), K(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> H[i];
        if (H[i] > 0) K[i] = (H[i] + D - 1) / D;
    }

    const ll INF = (1LL << 62);

    vector<char> infected(N, false);
    vector<ll> left_time(N, INF), right_time(N, INF), cand(N, INF);

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

    auto calc = [&](int i) -> ll {
        if (infected[i]) return INF;

        ll k = K[i];
        bool hasL = (left_time[i] != INF);
        bool hasR = (right_time[i] != INF);

        if (!hasL && !hasR) return INF;
        if (hasL && !hasR) return left_time[i] + k;
        if (!hasL && hasR) return right_time[i] + k;

        ll a = left_time[i], b = right_time[i];
        if (a > b) swap(a, b);

        if (a + k <= b) return a + k;
        return (k + a + b + 1) / 2;
    };

    auto relax = [&](int i) {
        if (i < 0 || i >= N || infected[i]) return;
        ll c = calc(i);
        if (c < cand[i]) {
            cand[i] = c;
            pq.emplace(c, i);
        }
    };

    ll ans = 0;

    for (int i = 0; i < N; i++) {
        if (H[i] <= 0) {
            infected[i] = true;
            ans++;
        }
    }

    for (int i = 0; i < N; i++) {
        if (!infected[i]) continue;

        if (i > 0 && !infected[i - 1]) {
            right_time[i - 1] = 0;
            relax(i - 1);
        }
        if (i + 1 < N && !infected[i + 1]) {
            left_time[i + 1] = 0;
            relax(i + 1);
        }
    }

    auto clean = [&]() {
        while (!pq.empty()) {
            auto [t, i] = pq.top();
            if (infected[i] || cand[i] != t) pq.pop();
            else break;
        }
    };

    ll expected = 1;

    while (true) {
        clean();

        if (pq.empty()) break;

        ll t = pq.top().first;
        if (t > expected) break;

        vector<int> group;

        while (true) {
            clean();
            if (pq.empty() || pq.top().first != t) break;

            auto [tt, i] = pq.top();
            pq.pop();

            if (!infected[i] && cand[i] == tt) {
                group.push_back(i);
            }
        }

        if (group.empty()) continue;

        for (int i : group) {
            if (!infected[i]) {
                infected[i] = true;
                ans++;
            }
        }

        for (int i : group) {
            if (i > 0 && !infected[i - 1]) {
                if (right_time[i - 1] > t) {
                    right_time[i - 1] = t;
                    relax(i - 1);
                }
            }
            if (i + 1 < N && !infected[i + 1]) {
                if (left_time[i + 1] > t) {
                    left_time[i + 1] = t;
                    relax(i + 1);
                }
            }
        }

        if (t == expected) expected++;
    }

    cout << ans << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.