提出 #76711679

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
using ll = long long;

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

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

    vector<ll> A(N), D(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> D[i];
    }

    // 计算每盏灯变暗的时间
    vector<ll> start(N);
    for (int i = 0; i < N; i++) {
        if (D[i] == 0) {
            start[i] = (A[i] <= K) ? 0 : 1e18;
        }
        else {
            if (A[i] <= K) {
                start[i] = 0;
            }
            else {
                start[i] = (A[i] - K + D[i] - 1) / D[i];
            }
        }
    }

    // 查询离线
    vector<pair<ll, int>> queries(Q);
    for (int j = 0; j < Q; j++) {
        ll t;
        cin >> t;
        queries[j] = { t, j };
    }
    sort(queries.begin(), queries.end());

    // 事件（变暗时间，位置）
    vector<pair<ll, int>> events(N);
    for (int i = 0; i < N; i++) events[i] = { start[i], i };
    sort(events.begin(), events.end());

    vector<ll> ans(Q);

    // 连续暗段: 左端点 -> 右端点
    map<int, int> segs;
    ll total = 0;

    auto add_len = [&](int len) {
        total += (ll)len * (len + 1) / 2;
        };
    auto sub_len = [&](int len) {
        total -= (ll)len * (len + 1) / 2;
        };

    int ev_idx = 0;
    for (int qid = 0; qid < Q; qid++) {
        ll cur_t = queries[qid].first;
        int idx = queries[qid].second;

        while (ev_idx < N && events[ev_idx].first <= cur_t) {
            int pos = events[ev_idx].second;
            ev_idx++;

            // 检查左右相邻段
            auto it = segs.upper_bound(pos);
            int right_len = 0, right_left = -1;
            if (it != segs.end() && it->first == pos + 1) {
                right_len = it->second - it->first + 1;
                right_left = it->first;
            }

            int left_len = 0, left_left = -1;
            if (it != segs.begin()) {
                auto prev_it = prev(it);
                if (prev_it->second == pos - 1) {
                    left_len = prev_it->second - prev_it->first + 1;
                    left_left = prev_it->first;
                }
            }

            // 移除左右段贡献
            if (left_len > 0) {
                sub_len(left_len);
                segs.erase(left_left);
            }
            if (right_len > 0) {
                sub_len(right_len);
                segs.erase(right_left);
            }

            // 合并新段
            int new_len = 1 + left_len + right_len;
            int new_left = (left_len > 0) ? left_left : pos;
            add_len(new_len);
            segs[new_left] = new_left + new_len - 1;
        }

        ans[idx] = total;
    }

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

    return 0;
}

提出情報

ジャッジ結果