https://kyopro.hateblo.jp/entry/2019/05/27/131647

問題. Roadwork

1次元上の原点に $Q$ 人の人がいる． $i$ 番目の人は時刻 $D_i$ に正の方向に速度 1 で進む．ただし，道路工事が行われている場所に到達するとこれ以上歩くのを止める．道路工事は $N$ 個行われており， $i$ 番目の道路工事は時刻 $S_i - 0.5$ から $T_i - 0.5$ の間に場所 $X_i$ で行われている．各人の歩いた距離を答えよ．ただし，無限に歩き続ける人の場合は -1 と答えよ．

制約： $1 \le N, Q \le 2 \times 10^5$ ，　 $0 \le S_i < T_i \le 10^9$ ，　 $1 \le X_i \le 10^9$ ，
　　　 $\,\, 0 \le D_1 < D_2 < \cdots < D_Q \le 10^9$

解法

$i$ 番目の人が $j$ 番目の道路工事の場所 $X_j$ に到達する時刻は $D_i + X_j$ である．また， $X_j$ に到達するときに工事中であるための必要十分条件は， $S_j - 0.5 \le D_i + X_j \le T_j - 0.5$ である．この不等式を整理すると $D_i$ が整数であることから， $D_i \in [S_j - X_j, T_j - X_j)$ となる．したがって， $D_1 < D_2 < \cdots < D_Q$ から， $j$ 番目の道路工事によって歩くことを止めてしまう人々は $D_{l_j}, D_{l_j + 1}, \ldots, D_{r_j}$ のように連続する区間となる． $j$ 番目の工事によって歩くのを止めてしまう人々の区間を $[l_j, r_j]$ と表すと，いくつかの工事でこれらの区間が交差する可能性があるが，人は最初に出会う工事中で歩くのを止めるので工事の場所で昇順に上の区間を求める．

各工事は工事の場所で昇順に整列されていると仮定する．現在 $j$ 番目の工事を考える．まだ歩くのを止めていない人々の列 $D$ に対して，上の $D_i \in [S_j - X_j, T_j - X_j)$ を満たす連続する部分を探索して，その部分を $D$ から削除する． $D$ は std::set で実装することによって，区間の探索を $O(\log Q)$ 時間ででき，区間に含まれる要素の削除を $O((r_j - l_j + 1) \log Q)$ 時間でできる．したがって，全体で $O(N \log N + Q \log Q)$ 時間で求まる．

計算時間： $O(N \log N + Q \log Q)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

void Solve() {
    int n, q;
    cin >> n >> q;

    vector<tuple<int, int, int>> stx(n);
    for (int i = 0; i < n; ++i)
        cin >> get<1>(stx[i]) >> get<2>(stx[i]) >> get<0>(stx[i]);

    sort(stx.begin(), stx.end());

    set<pair<int, int>> d;
    for (int i = 0, x; i < q; ++i) {
        cin >> x;
        d.emplace(x, i);
    }

    vector<ll> tm(q, -1);
    for (int i = 0; i < n; ++i) {
        auto first = d.lower_bound(make_pair(get<1>(stx[i]) - get<0>(stx[i]), 0));
        auto end= d.upper_bound(make_pair(get<2>(stx[i]) - get<0>(stx[i]) - 1, q));

        for (auto it = first; it != end; ++it) tm[it->second] = get<0>(stx[i]);

        d.erase(first, end);
    }

    for (int i = 0; i < q; ++i) cout << tm[i] << '\n';
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    Solve();

    return 0;
}

set の使い方に手間取ったのでしっかり復習．