P9404 [POI 2020/2021 R3] Snow Sweeper Porter / Surowa zima

Translated from [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Surowa zima](https://szkopul.edu.pl/problemset/problem/QCCQf92wAoWAOoJ3tHoypvp3/statement/)。 d1t3。

There is a road of length $l$ meters (a number line). There are $n$ charging stations on the road. Every day, the entire road (coordinates $[0,l]$) is covered with snow. There is a machine that can clear snow. With one charge, it can clear at most $k$ meters of snow. Snow clearing is done at the same time as moving; see the sample explanation. The machine can move 1 meter per second, and charging takes no time. In short, **moving without clearing snow does not consume energy and takes 1 second; moving while clearing snow consumes $\bold{\frac1k}$ of the maximum energy and takes 1 second; clearing snow requires moving.** You are given the machine’s initial position each day. The machine starts with no energy. For each day, find the minimum time to clear all the snow. The final position can be anywhere. There are updates: charging stations may break or be repaired (before day 1, all are working), but it is guaranteed that every day there is at least one working charging station (so it is never impossible to finish).

The first line contains four integers $n,l,k,d$. The second line contains $n$ integers $x_1,x_2,\dots,x_n$, representing the positions of the charging stations. It is guaranteed that $0\leq x_1

Output $d$ lines, each with one integer, the answer for that day.

Sample explanation: $3\rightarrow2_{充电}\Rightarrow0\rightarrow2_{充电}\Rightarrow4\rightarrow5_{充电}\Rightarrow4$。$\rightarrow$ means moving, and $\Rightarrow$ means moving while clearing snow. Constraints: for all testdata, $1\leq n\leq 250000$, $1\leq l\leq 10^9$, $1\leq k\leq l$, $1\leq d\leq 250000$, $\sum z,\sum u\leq 500000$. | Subtask ID | Additional Constraints | Score | | :----------: | :----------: | :----------: | | 1 | $l\leq 12$，$d\leq 50$ | 10 | | 2 | $l\leq 500$，$d\leq 50$，$k=1$ | 12 | | 3 | $l\leq 5000000$，$d\leq 20$ | 8 | | 4 | $z=u=0$ | 8 | | 5 | $z,u\leq 100$，$k\leq 50$ | 20 | | 6 | $k=1$ | 18 | | 7 | | 24 | Translated by ChatGPT 5