Overview

This problem asks us to find the number of residents who will eventually be infected in an infection simulation spreading among residents lined up in one dimension. We are given each resident’s immunity \(H_i\) and the damage \(D\) received from adjacent infected residents.

A naive round-by-round simulation is too slow to pass within the time limit because it could take more than \(10^9\) rounds in the worst case. Therefore, we solve this by applying Dijkstra’s algorithm (shortest path algorithm) to quickly find the earliest round in which each resident gets infected.

---

Analysis

1. Why Naive Simulation Fails

The initial immunity \(H_i\) of a resident can be up to \(10^9\), and the damage \(D\) subtracted per round can be as small as \(1\). For example, if residents are lined up in a single row and the infection spreads sequentially from one end with \(D=1\), it would require \(10^9\) or more rounds of calculation in the worst case. Thus, a simple simulation that updates states round-by-round (with a time complexity of \(O(N \times \text{ラウンド数})\)) will result in TLE (Time Limit Exceeded).

2. Reduction to Dijkstra’s Algorithm

The spread of infection is a process where “damage” propagates from already infected adjacent residents. This is highly similar to the shortest path problem on a graph. For each resident \(i\), we define dist[i] as the “earliest round in which they get infected”.

Residents who initially have \(H_i \leq 0\) will be infected at round \(0\) (dist[i] = 0). Using these as starting points, we can determine the infection rounds in order from the earliest, similar to Dijkstra’s algorithm, and update the infection rounds of adjacent uninfected residents.

3. Calculating the Infection Round from Adjacent Residents

Let \(p_1, p_2\) (\(p_1 \leq p_2\)) be the infection rounds of the already infected adjacent residents of resident \(v\). The round in which resident \(v\) gets infected is the minimum of the following three cases:

Case A: 0 adjacent infected residents

Naturally, they will never be infected. The infection round is infinity (\(\infty\)).

Case B: 1 adjacent infected resident (or affected by only one side)

They receive \(D\) damage every round from the infected resident. The number of rounds required is \(\lceil H_v / D \rceil\). Therefore, the infection round is \(p_1 + \lceil H_v / D \rceil\).

Case C: 2 adjacent infected residents

The situation changes depending on the difference in their infection times, \(diff = p_2 - p_1\).

• When \(diff \geq \lceil H_v / D \rceil\) Before the second resident is infected, \(v\) gets infected solely by the damage from the first resident. Thus, this is practically the same as Case B.
• When \(diff < \lceil H_v / D \rceil\) During the first \(diff\) rounds, they receive damage only from the first resident (totaling \(diff \times D\)). After that (from round \(p_2\) onwards), they receive \(2D\) damage every round from both neighbors. The remaining immunity at round \(p_2\) is \(rem\_H = H_v - diff \times D\). Since it decreases by \(2D\) every round from this point, the additional number of rounds required is \(\lceil rem\_H / (2D) \rceil\). Therefore, the infection round is \(p_2 + \lceil rem\_H / (2D) \rceil\).

4. Handling the Termination Condition of Propagation

The problem description contains an important rule: “If there are no residents newly infected in this round, the propagation terminates immediately.”

The dist[i] obtained by Dijkstra’s algorithm is the infection round assuming that propagation continues indefinitely. However, if the number of newly infected residents becomes \(0\) in some round \(r\), no subsequent rounds will occur. In other words, residents who were supposed to be infected in round \(r\) or later will actually remain uninfected.

To determine this, we collect all reachable infection rounds, sort them, and remove duplicates to create a list times. For the actual infection to continue without interruption, the rounds must exist continuously as \(0, 1, 2, \dots, k\). For example, if \(2\) is missing as in times = [0, 1, 3], it means there were \(0\) newly infected residents in round \(2\), so no infections will occur from round \(3\) onwards. Therefore, letting \(k\) be the maximum \(i\) that satisfies times[i] == i, only residents with dist[i] <= k will eventually be infected.

---

Algorithm

1. Initialization:
   • Initialize the dist array with infinity (INF).
   • For resident \(i\) with \(H_i \leq 0\) in the initial state, set dist[i] = 0 and add them to the priority queue pq.
2. Finding the Earliest Rounds with Dijkstra’s Algorithm:
   • Extract the resident \(u\) with the earliest infection round from pq.
   • For each adjacent resident \(v \in \{u-1, u+1\}\), add the already determined infection round of the neighbor to parent_vals[v], and calculate the new infection round of \(v\) using the function calc_next(v).
   • If the calculated value is smaller than the current dist[v], update it and add \(v\) to pq.
3. Checking the Termination Condition:
   • Collect non-INF values from the obtained dist array, sort and remove duplicates, and find the maximum continuous round \(k\).
4. Aggregation:
   • Count and output the number of residents with dist[i] <= k.

---

Complexity

• Time Complexity: \(O(N \log N)\)
  • For \(N\) residents, the number of vertices in the graph is \(N\) and the number of edges is at most \(2N\).
  • The number of priority queue operations in Dijkstra’s algorithm is \(O(N)\), and each operation takes \(O(\log N)\) time.
  • The calculation of calc_next can be done in \(O(1)\) time.
  • The final sorting and duplicate removal can also be executed in \(O(N \log N)\) time.
• Space Complexity: \(O(N)\)
  • It uses \(O(N)\) memory to store arrays such as dist, visited, and parent_vals.

---

Key Implementation Points

• Trick for Ceiling Division:

  • To compute \(\lceil A / B \rceil\) using integer arithmetic, the technique (A + B - 1) / B is used. This avoids precision issues associated with floating-point numbers.

• Beware of Overflow:

  • \(H_i\) and \(D\) can be up to \(10^9\), and values can become extremely large during calculations. In C++, you should use the long long type and set the constant INF representing infinity to a sufficiently large value (such as 4e18 in the code).

    Source Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 4e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;

    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }

    vector<long long> dist(N, INF);
    vector<bool> visited(N, false);
    vector<vector<long long>> parent_vals(N);

    using PLI = pair<long long, int>;
    priority_queue<PLI, vector<PLI>, greater<PLI>> pq;

    for (int i = 0; i < N; ++i) {
        if (H[i] <= 0) {
            dist[i] = 0;
            pq.push({0, i});
        }
    }

    auto calc_next = [&](int v) -> long long {
        if (H[v] <= 0) return 0;
        const auto& p = parent_vals[v];
        if (p.empty()) return INF;
        long long steps1 = (H[v] + D - 1) / D;
        if (p.size() == 1) {
            return p[0] + steps1;
        }
        long long p1 = p[0];
        long long p2 = p[1];
        long long d1 = p1 + steps1;
        long long d2 = p2 + steps1;

        long long p_max = max(p1, p2);
        long long p_min = min(p1, p2);
        long long diff = p_max - p_min;

        long long d3;
        if (diff >= steps1) {
            d3 = p_min + steps1;
        } else {
            long long rem_H = H[v] - diff * D;
            long long steps3 = (rem_H + 2 * D - 1) / (2 * D);
            d3 = p_max + steps3;
        }
        return min({d1, d2, d3});
    };

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (int v : {u - 1, u + 1}) {
            if (v < 0 || v >= N) continue;
            if (visited[v]) continue;

            parent_vals[v].push_back(d);
            long long new_d = calc_next(v);
            if (new_d < dist[v]) {
                dist[v] = new_d;
                pq.push({dist[v], v});
            }
        }
    }

    vector<long long> times;
    for (int i = 0; i < N; ++i) {
        if (dist[i] != INF) {
            times.push_back(dist[i]);
        }
    }

    if (times.empty()) {
        cout << 0 << "\n";
        return 0;
    }

    sort(times.begin(), times.end());
    times.erase(unique(times.begin(), times.end()), times.end());

    long long k = 0;
    for (size_t i = 0; i < times.size(); ++i) {
        if (times[i] == (long long)i) {
            k = i;
        } else {
            break;
        }
    }

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        if (dist[i] <= k) {
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.