ABC128 E Roadwork

問題ページ

解法

人々は整数時刻に座標を出発し、速度で正の方向に歩き続けます。よって、時刻から時刻まで座標を通行止めにするということは、時刻に出発した人は座標で通行止めに当たるということになります。人々が歩いている途中に通行止めに当たった場合はそこで歩くのをやめるので、出発する時刻を被覆する区間のうち最も小さいまで歩き続けるということになります（そのような区間がなければ無限に歩き続けます）。これは遅延評価セグメント木を使えば解くことができます。時刻はそのままでは使えないので座標圧縮をしますが、このとき工事関連の時刻だけではなく、人々が出発する時刻もまとめて座圧すると実装が楽になります。セグ木の更新順は、各クエリでは最小のを求めたいのでの大きい順に更新します。以下の実装では区間取得を行うセグ木を用いていますが、この問題では一点取得に対応していれば十分です。

実装

提出コード - https://atcoder.jp/contests/abc128/submissions/6933093
work:=第一成分が、第二成分の第一成分が、第二成分の第二成分が

#include<iostream>
#include<vector>
#include<limits>
#include<unordered_map>
#include<algorithm>
#include<utility>
using namespace std;

using work = pair<int, pair<int, int> >;

constexpr int INF = 1 << 30;

// 区間更新区間min
template<class T>
class SegmentTree{
    int n;
    vector<T> node, upd;
    vector<bool> flag;

    void evaluate(int k, int l, int r){
        if(flag[k]){
            node[k] = upd[k];
            flag[k] = false;
            if(r - l > 1){
                upd[k * 2 + 1] = upd[k];
                flag[k * 2 + 1] = true;
                upd[k * 2 + 2] = upd[k];
                flag[k * 2 + 2] = true;
            }
        }
        return;
    }

    void update(int a, int b, int k, int l, int r, T x){
        evaluate(k, l, r);
        if(b <= l || r <= a){
            return;
        }
        if(a <= l && r <= b){
            upd[k] = x;
            flag[k] = true;
            evaluate(k, l, r);
            return;
        }

        update(a, b, k * 2 + 1, l, (l + r) / 2, x);
        update(a, b, k * 2 + 2, (l + r) / 2, r, x);

        node[k] = min(node[k * 2 + 1], node[k * 2 + 2]);

        return;
    }

    T get(int a, int b, int k, int l, int r){
        evaluate(k, l, r);
        if(b <= l || r <= a){
            return numeric_limits<T>::max();
        }
        if(a <= l && r <= b){
            return node[k];
        }

        T vl = get(a, b, k * 2 + 1, l, (l + r) / 2);
        T vr = get(a, b, k * 2 + 2, (l + r) / 2, r);

        return min(vl, vr);
    }

public:
    // 要素数または配列でコンストラクト
    SegmentTree(int siz = 0){
        init(siz);
    }

    SegmentTree(const vector<T> v){
        build(v);
    }

    // 指定された要素数で初期化
    void init(int siz){
        n = 1;
        while(n < siz){
            n <<= 1;
        }

        node.resize(n * 2 - 1);
        fill(node.begin(), node.end(), numeric_limits<T>::max());

        upd.resize(n * 2 - 1);

        flag.resize(n * 2 - 1);
        fill(flag.begin(), flag.end(), false);

        return;
    }

    // 指定された配列で初期化
    void build(const vector<T> v){
        init((int)v.size());

        for(int i = 0, i_len = (int)v.size() ; i < i_len ; ++i){
            node[i + n - 1] = v[i];
        }

        for(int i = n - 2 ; i >= 0 ; --i){
            node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);
        }

        return;
    }

    // [a, b)をxに更新
    void update(int a, int b, T x){
        update(a, b, 0, 0, n, x);
        return;
    }

    // [a, b)の取得
    T get(int a, int b){
        return get(a, b, 0, 0, n);
    }
};

template<typename T>
int compress(vector<T> v, unordered_map<T, int> &zip){
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 0, i_len = (int)v.size() ; i < i_len ; ++i){
        zip[v[i]] = i;
    }
    return (int)v.size();
}

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

    int n, q;
    cin >> n >> q;

    vector<int> ti;

    vector<work> v;
    for(int i = 0 ; i < n ; ++i){
        int s, t, x;
        cin >> s >> t >> x;
        v.push_back({x, {s - x, t - x}});
        ti.push_back(s - x);
        ti.push_back(t - x);
    }

    vector<int> query;
    for(int i = 0 ; i < q ; ++i){
        int d;
        cin >> d;
        query.push_back(d);
        ti.push_back(d);
    }

    unordered_map<int, int> zip;
    int m = compress(ti, zip);

    SegmentTree<int> seg(m);

    sort(v.begin(), v.end(), [](work l, work r){ return l.first > r.first; });
    for(int i = 0 ; i < n ; ++i){
        seg.update(zip[v[i].second.first], zip[v[i].second.second], v[i].first);
    }

    for(auto &d : query){
        int ans = seg.get(zip[d], zip[d] + 1);
        if(ans < INF){
            cout << ans << endl;
        }else{
            cout << -1 << endl;
        }
    }

    return 0;
}