概要

各街灯が「何日目に暗くなるか」を先に計算し、問い合わせ日 \(T\) を小さい順に処理しながら、暗くなった街灯を順次有効化していきます。
有効化された（=暗い）街灯の連続成分を Union-Find で管理し、暗い部分区間数を高速に更新します。

考察

この問題で直接やりたくなるのは、各問い合わせごとに全街灯について
「\(C_i(T_j) \le K\) か？」を判定し、暗い連続区間の長さから部分区間数を数える方法です。
しかしこれは \(O(NQ)\) になり、\(N+Q \le 2\times 10^5\) では間に合いません。

重要な観察 1：各街灯は一度暗くなったらずっと暗い

明るさは \(C_i(t)=\max(0, A_i-D_i t)\) で単調非増加です。
したがって「暗いかどうか」は時刻に対して false -> true に一度だけ変化します（もしくはずっと false / ずっと true）。

つまり各街灯 \(i\) について、
- いつ暗くなるか（最小の \(t\)）を前計算できる。

条件 \(A_i-D_i t \le K\) より、 - もともと \(A_i \le K\) なら \(t=0\) で暗い - \(A_i > K, D_i=0\) なら永遠に暗くならない - それ以外は
\(t \ge \dfrac{A_i-K}{D_i}\) なので
最小整数時刻は
\(t_i=\left\lceil\dfrac{A_i-K}{D_i}\right\rceil =\dfrac{(A_i-K)+D_i-1}{D_i}\)（切り上げ）

重要な観察 2：問い合わせを時刻順に見れば「追加」だけになる

問い合わせ \(T_j\) を昇順に処理すると、時刻が進むにつれ暗い街灯は増えるだけです。
よって「暗くなった街灯を有効化する」イベント処理ができます。

重要な観察 3：求めたい値は連続成分サイズで管理できる

暗い街灯だけを 1 とする配列を考えると、答えは
「各連続 1 区間の長さを \(m\) として \(\frac{m(m+1)}{2}\) の総和」です。

街灯を1本有効化したときに影響があるのは隣だけなので、Union-Find で連続成分を管理すると更新が高速です。
成分サイズを \(s\) とすると寄与は \(\frac{s(s+1)}{2}\)。
2成分を併合するときは - 旧寄与2つを引く - 新寄与1つを足す
で全体値を保てます。

アルゴリズム

1. 各街灯 \(i\) について「暗くなる日」\(t_i\) を計算し、events = (t_i, i) に入れる（永遠に暗くならないものは入れない）。
2. 問い合わせも (T_j, 元の番号) として保存。
3. events と queries をともに時刻昇順にソート。
4. Union-Find と active[i]（その街灯が暗いか）を用意し、cur を現在の暗い部分区間数として持つ。
5. 各問い合わせ時刻 \(T\) について：
   • event.day <= T の街灯をすべて有効化
     
   • 有効化時：
     • まず単独成分として追加（cur += 1）
     • 左右の有効な隣と Union
     • Union 時に \(\frac{s(s+1)}{2}\) の差分更新
   • その時点の cur が答え
6. 元の問い合わせ順に戻して出力。

計算量

• 時間計算量: \(O((N+Q)\log(N+Q))\)（ソートが支配的。Union-Find はほぼ線形）
• 空間計算量: \(O(N+Q)\)

実装のポイント

• 切り上げ計算は t = (num + D - 1) / D を使う（num = A-K）。

• D=0 のときの分岐を忘れない（暗くならない可能性がある）。

• 答えは最大で大きくなるので long long を使う。

• active を見て二重有効化を防ぐ（このコードでは安全のためチェック済み）。

• Union-Find の併合時に、寄与更新の順序（引いてから足す）を正しく実装する。

  ソースコード

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

struct DSU {
    int n;
    vector<int> p, sz;
    long long cur = 0; // total number of all-dark subsegments
    DSU(int n=0): n(n), p(n+1), sz(n+1,0) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x){
        while(p[x] != x){
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    void activate(int x, const vector<char>& active){
        p[x] = x;
        sz[x] = 1;
        cur += 1; // new single segment
        if(x > 1 && active[x-1]) unite(x, x-1);
        if(x < n && active[x+1]) unite(x, x+1);
    }
    void unite(int a, int b){
        a = find(a); b = find(b);
        if(a == b) return;
        if(sz[a] < sz[b]) swap(a,b);
        // remove old contributions
        cur -= 1LL * sz[a] * (sz[a] + 1) / 2;
        cur -= 1LL * sz[b] * (sz[b] + 1) / 2;
        p[b] = a;
        sz[a] += sz[b];
        // add new contribution
        cur += 1LL * sz[a] * (sz[a] + 1) / 2;
    }
};

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

    int N, Q;
    long long K;
    cin >> N >> Q >> K;

    vector<pair<long long,int>> events; // (day when becomes dark, index)
    events.reserve(N);

    for(int i=1;i<=N;i++){
        long long A,D;
        cin >> A >> D;
        if(A <= K){
            events.push_back({0, i});
        }else{
            if(D == 0){
                // never dark
            }else{
                // need smallest t >= 0 s.t. A - D*t <= K => t >= (A-K)/D
                long long num = A - K;
                long long t = (num + D - 1) / D;
                events.push_back({t, i});
            }
        }
    }

    vector<pair<long long,int>> queries(Q); // (T, original index)
    for(int j=0;j<Q;j++){
        long long T;
        cin >> T;
        queries[j] = {T, j};
    }

    sort(events.begin(), events.end());
    sort(queries.begin(), queries.end());

    vector<long long> ans(Q, 0);
    vector<char> active(N+2, 0);
    DSU dsu(N);

    int ei = 0, E = (int)events.size();
    for(auto &qq : queries){
        long long T = qq.first;
        int qi = qq.second;
        while(ei < E && events[ei].first <= T){
            int idx = events[ei].second;
            if(!active[idx]){
                active[idx] = 1;
                dsu.activate(idx, active);
            }
            ei++;
        }
        ans[qi] = dsu.cur;
    }

    for(int i=0;i<Q;i++){
        cout << ans[i] << '\n';
    }
    return 0;
}

---

この解説は gpt-5.3-codex によって生成されました。