これと似てる！！！
これの解法 3 みたいなやり方をイベントソートって呼ぶのね。

問題概要 (意訳)

$10^{9}$ くらいのサイズの配列があって最初は INF に初期化されている。 $N$ 回の以下の操作を行う

整数 $S_{i}, T_{i}, X_{i}$ が与えられて、区間 [ $S_{i} - X_{i}, T_{i} - X_{i}$ ) 全体を $X_{i}$ と比較して小さい方で置き換える

このあと、以下の $Q$ 個のクエリに答えよ

$D_{i}$ の位置の値を答えよ。

制約

$1 \le N, Q \le 2 \times 10^{5}$

考えたこと

大体この問題と一緒なので、この問題に対応した 3 つの解法がそれぞれ使える。ここでは解法 3: イベントソートでやってみる。

drken1215.hatenablog.com

まさにいもす法の「区間加算」ならぬ「区間 chmin」バージョンという感じ！！！

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using type = pair<int, long long>; // 1: query, 0; delete, -1: insert
using event = pair<long long, type>;

int main() {
    int N, Q; cin >> N >> Q;
    vector<event> v;
    for (int i = 0; i < N; ++i) {
        int s, t, x; cin >> s >> t >> x;
        v.push_back({s-x, type(-1, x)});
        v.push_back({t-x, type(0, x)});
    }
    for (int i = 0; i < Q; ++i) {
        int d; cin >> d;
        v.push_back({d, type(1, i)});
    }
    sort(v.begin(), v.end());

    vector<long long> res(Q);
    multiset<long long> se;
    for (auto p : v) {
        long long x = p.first;
        int type = p.second.first;
        long long val = p.second.second;
        if (type == -1) se.insert(val);
        else if (type == 0) se.erase(se.lower_bound(val));
        else res[val] = (se.empty() ? -1 : *(se.begin()));
    }
    for (auto v : res) cout << v << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 128 E - Roadwork (青色, 500 点)

問題概要 (意訳)

制約

考えたこと