题解

每辆车怎么走是确定的：到绿灯就过，到红灯就等．困难在于车辆很多，如果每辆车都从头走一遍，会重复计算很多次相同的后半段路程．

先直接模拟

设当前时刻为 $t$．走到第 $i$ 盏灯时，先令 $t\leftarrow t+d_i$．若 $t\bmod P\ge g_i$，说明遇到了红灯，再加上 $P-t\bmod P$ 秒的等待时间．处理完所有灯，最后加上 $d_{n+1}$．

这就是题目规定的行驶过程，时间复杂度 $O(nq)$，保存道路和交通灯需要 $O(n)$ 空间．子任务 $1$ 和 $2$ 中，$nq$ 都不超过 $4\times 10^6$，这样可以拿到 $35$ 分．

出发时间只差整周期时，过程也只差整周期

两辆车的出发时间如果相差 $P$ 秒，它们到每盏灯的时间也会相差 $P$ 秒．因为灯的状态完全一样，等待的时间也一样．所以可以先模拟出发时刻 $0,1,\ldots,P-1$，把结果存下来．

若时刻 $r$ 出发的到达时刻为 $b_r$，那么时刻 $t$ 出发的答案就是

$$t-(t\bmod P)+b_{t\bmod P}.$$

预处理 $O(nP)$，每个询问 $O(1)$，空间 $O(n+P)$．这能通过子任务 $3$；与直接模拟结合，可以拿到 $55$ 分．这里不需要把每盏灯、每个余数的状态全部存下来，直接枚举出发余数并模拟即可．

每段行驶时间都是周期的倍数

在子任务 $4$ 中，行驶不会改变当前时刻除以 $P$ 的余数．设出发余数为 $r$：

• 如果 $r<\min_i g_i$，每一盏灯都是绿灯，不需要等待；
• 否则，迟早会遇到一盏红灯，等待 $P-r$ 秒后，余数变为 $0$．后面的行驶不会改变余数，而所有灯在余数为 $0$ 时都是绿灯，因此再也不用等待．

把总行驶时间加上这一次可能存在的等待时间，就是答案．预处理总行驶时间和最小的 $g_i$ 后，时间复杂度为 $O(n+q)$，辅助空间可以为 $O(1)$．这能通过子任务 $4$；把前三种做法按适用条件组合起来，可以拿到 $70$ 分．

等过一次红灯之后，后面的路程可以共用

下面考虑完整数据．周期太大，不能枚举每一个余数，但可以只保存真正有用的状态．

假设两辆车都在第 $i$ 盏灯前等过红灯．它们离开这盏灯时，时刻一定都是 $P$ 的倍数．虽然绝对时刻可能不同，但后面每一盏灯的状态变化完全相同，剩余的行驶和等待时间也相同．

因此，令 $f_i$ 表示：在一个周期刚开始时从第 $i$ 盏灯出发，到达终点还需要多少秒． 这里已经通过了第 $i$ 盏灯，只考虑它后面的灯．

再令 $D_i=d_1+\cdots+d_i$，即从起点到第 $i$ 盏灯完全不等待时的行驶时间；$D_{n+1}$ 是全程的行驶时间．

求 $f_i$ 时，先沿路找下一盏会遇到红灯的交通灯，设为 $j$．在遇到它之前没有等待，因此到它的行驶时间恰好是

$$\Delta=D_j-D_i.$$

出发时余数为 $0$，所以到第 $j$ 盏灯时的余数就是 $\Delta\bmod P$．等到下个周期开始后，余下的时间已经由 $f_j$ 记录好了．于是

$$f_i=\Delta+\bigl(P-\Delta\bmod P\bigr)+f_j.$$

如果后面没有任何红灯，则 $f_i=D_{n+1}-D_i$．

这里 $j>i$，所以从后向前求 $f_i$ 就行．而且 $j$ 是确定会遇到红灯的地方，余数不可能为 $0$，因此等待时间不会凭空多出一个周期．

现在问题只剩下一个：怎样快速找到下一盏会拦住车辆的灯？

一盏灯会拦住哪些出发余数

先假设一路都不等待．把到第 $j$ 盏灯的时刻写成

$$h+D_j.$$

从起点时刻 $t$ 出发时，$h=t$．而计算 $f_i$ 时，从第 $i$ 盏灯的余数 $0$ 出发，到第 $j$ 盏灯的余数是 $(D_j-D_i)\bmod P$，所以此时把 $h$ 的余数设成 $(-D_i)\bmod P$ 就可以了．这只是用于计算灯的状态，不是让车辆真的在负数时刻出发．

第 $j$ 盏灯是红灯，当且仅当

$$(h+D_j)\bmod P\in[g_j,P-1].$$

也就是说，让右侧的每个红灯余数减去 $D_j$，就得到了会被这盏灯拦住的 $h$ 的余数．它们在模 $P$ 的圆环上组成一个连续区间：

$$[g_j-D_j,\ P-1-D_j]\pmod P.$$

把两个端点都调整到 $[0,P-1]$，记为 $l,r$．若 $l\le r$，就是普通区间 $[l,r]$；若 $l>r$，说明经过了余数 $0$，拆成 $[l,P-1]$ 和 $[0,r]$．当 $g_j=P$ 时，这盏灯没有红灯区间，不能按上述端点硬凑成一个区间．

注意，我们只用“不等待”的假设来找第一次红灯．在它之前本来就没有等待，所以找到的这盏灯是准确的；此后的等待交给 $f_j$ 处理，不再沿用原来的 $h$．

倒着加入交通灯，维护最近的拦截位置

想象有一个按余数编号的数组．数组的第 $h$ 项记录：从当前已经加入的灯中看，余数为 $h$ 的车最先会被哪盏灯拦住．没有则记录 $n+1$．

从第 $n$ 盏灯往前加入．加入第 $i$ 盏灯时，它比已经加入的灯都靠前，所以在它自己的红灯区间内，答案直接改为 $i$；区间外保持不变．这就是区间赋值、单点查询．

处理第 $i$ 盏灯的顺序是：

1. 此时只有 $i$ 后面的灯已经加入，查询 $(-D_i)\bmod P$，得到下一次等待的位置 $j$．
2. 用刚才的转移求出 $f_i$．
3. 把第 $i$ 盏灯的红灯区间赋值为 $i$．

顺序不能反过来，否则查询会把自己也算进去．

这个数组的值域太大，但我们真正会查询的位置只有两类：求 $f_i$ 时的 $(-D_i)\bmod P$，以及回答方案时的 $t_j\bmod P$．把这至多 $n+q$ 个余数排序去重，用线段树维护即可．

对一个普通区间 $[l,r]$，二分找到离散数组中第一个不小于 $l$ 的位置，以及最后一个不大于 $r$ 的位置，对这段下标赋值．区间内如果没有查询余数，就不需要修改．不必把红灯区间的端点也加进离散数组．

线段树中，一个节点若整段都对应同一盏灯，就保存这盏灯的编号；否则保存标记 $0$，继续向下查询．区间赋值覆盖原标记，单点查询返回经过节点上的有效标记即可．

最后回答每个出发方案

所有灯都加入后，查询 $t\bmod P$，得到第一次需要等待的位置 $j$．

• 若 $j=n+1$，全程不等，答案是 $t+D_{n+1}$．
• 否则，第一次到第 $j$ 盏灯的时刻为 $v=t+D_j$．等待到新周期开始，再接上 $f_j$，答案是 $v+(P-v\bmod P)+f_j$．

区间维护始终记录编号最小的拦截灯，所以第一次等待的位置正确；从后向前计算时，转移所需的 $f_j$ 都已算出；等待后统一从余数 $0$ 出发，保证接上 $f_j$ 不会丢失信息．这三个条件连起来，就覆盖了每辆车的完整行驶过程．

每盏灯做一次查询和至多两次赋值，每个方案再做一次查询．加上排序，时间复杂度为 $O((n+q)\log(n+q))$，空间复杂度为 $O(n+q)$，可以通过全部子任务．

实现时，累计行驶时间、$f_i$ 和答案都要用 long long．负数取模要调整到 $[0,P-1]$；判断红灯要包含余数等于 $g_i$ 的情况．

参考代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct SegTree {
    int n;
    vector<int> tag;
    SegTree(int n, int value) : n(n), tag(n * 4, value) {}
    void push(int p) {
        if (tag[p]) {
            tag[p * 2] = tag[p * 2 + 1] = tag[p];
            tag[p] = 0;
        }
    }
    void change(int l, int r, int value, int s, int t, int p) {
        if (l <= s && t <= r) {
            tag[p] = value;
            return;
        }
        push(p);
        int mid = (s + t) / 2;
        if (l <= mid) change(l, r, value, s, mid, p * 2);
        if (r > mid) change(l, r, value, mid + 1, t, p * 2 + 1);
    }
    int query(int x, int s, int t, int p) const {
        if (tag[p]) return tag[p];
        int mid = (s + t) / 2;
        if (x <= mid) return query(x, s, mid, p * 2);
        return query(x, mid + 1, t, p * 2 + 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    ll P;
    cin >> n >> q >> P;
    vector<ll> d(n + 2), g(n + 1), f(n + 1), t(q), xs;
    for (int i = 1; i <= n + 1; i++) {
        cin >> d[i];
        d[i] += d[i - 1];
    }
    for (int i = 1; i <= n; i++) cin >> g[i];
    auto mod = [&](ll x) { return (x % P + P) % P; };
    for (int i = 1; i <= n; i++) xs.push_back(mod(-d[i]));
    for (ll &x : t) {
        cin >> x;
        xs.push_back(x % P);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    int len = (int)xs.size();
    SegTree tr(len, n + 1);
    auto get = [&](ll x) {
        int pos = (int)(lower_bound(xs.begin(), xs.end(), x) - xs.begin());
        return tr.query(pos, 0, len - 1, 1);
    };
    auto put = [&](ll l, ll r, int value) {
        int a = (int)(lower_bound(xs.begin(), xs.end(), l) - xs.begin());
        int b = (int)(upper_bound(xs.begin(), xs.end(), r) - xs.begin()) - 1;
        if (a <= b) tr.change(a, b, value, 0, len - 1, 1);
    };
    for (int i = n; i >= 1; i--) {
        // 此时只加入了 i 后面的灯，先求 f[i]，再加入第 i 盏灯。
        int j = get(mod(-d[i]));
        if (j == n + 1) f[i] = d[n + 1] - d[i];
        else {
            ll travel = d[j] - d[i];
            f[i] = travel + P - travel % P + f[j];
        }
        if (g[i] == P) continue;
        ll l = mod(g[i] - d[i]), r = mod(P - 1 - d[i]);
        if (l <= r) put(l, r, i);
        else {
            put(l, P - 1, i);
            put(0, r, i);
        }
    }
    for (ll x : t) {
        int j = get(x % P);
        if (j == n + 1) cout << x + d[n + 1] << '\n';
        else {
            ll arrival = x + d[j];
            cout << arrival + P - arrival % P + f[j] << '\n';
        }
    }
    return 0;
}