P9404 [POI 2020/2021 R3] 扫雪波特 / Surowa zima

译自 [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。

有一条长 $l$ 米的道路（数轴）。路上有 $n$ 个充电站。每天整条路上（坐标 $[0,l]$）都会落满雪。 有一台机器能扫雪。充一次电可以扫至多 $k$ 米的雪。扫雪是和移动同时进行的，详见样例解释。机器一秒能移动一米，充电不消耗时间。 简单来说，**移动不扫雪不消耗电，需要一秒；移动并扫雪消耗最大电量的 $\bold{\frac1k}$，需要一秒；扫雪必须移动。** 给出每天机器的初始位置，机器初始没电，问每天清除所有雪的最少时间。终点任意。 带修，即充电站可能损坏或修好（第一天之前都是好的），但保证每天都至少有一个好的充电站（所以不会无解）。

第一行四个整数 $n,l,k,d$。 第二行 $n$ 个整数 $x_1,x_2,\dots,x_n$，表示充电站的位置，保证 $0\leq x_1

$d$ 行，每行一个整数，表示每天的答案。

样例解释：$3\rightarrow2_{充电}\Rightarrow0\rightarrow2_{充电}\Rightarrow4\rightarrow5_{充电}\Rightarrow4$。$\rightarrow$ 表示移动，$\Rightarrow$ 表示移动并扫雪。 对于所有数据，$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$。 | 子任务编号 | 附加限制 | 分数 | | :----------: | :----------: | :----------: | | 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 |