エレベータ [RUPC2018 Day1 G]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp18Day1/problems/G

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day1/2755717

クエリとエレベータを時系列順にソートしておく。
クエリを処理していくが、時系列順に処理を行って答えを出し、最後にクエリの順番で答えるようにする。
以下のコードでは、indexだけが入った配列（ord配列）を用意し、ソートして、それをつかって時系列順に処理を行っている。
　
まず、S[i]≧T[i]であれば、階段を降りることで到達可能である。
そうでないなら、エレベータを使用する必要がある。
i番目のクエリを処理しているとすると、E[i]日の昼より前にできているエレベータの区間は全て自由に行き来できるようになる。
エレベータによって行き来できる所を連結しておくと、S[i]からT[i]へ到達可能であるとは、S[i]とT[i]が同じ連結成分に属すると言い換えられる。
クエリを時系列順に処理しているので、エレベータの連結も時系列順に行っていけばいい。
クエリを処理していくと時間が経過していく感じになるので、答えを出す前にその都度エレベ―タを作っていくようにしていく。
　
さて、残った問題は「A[i]～B[i]の区間を連結する」と「S[i]とT[i]が同じ連結成分に属するかの判定」の2つである。
連結系で思いつくのがUnionFindであるが、毎回連結処理でO(N)かかる。
隣接する区間の連結は、setで区間を管理するテクを使うことで実現できる。
区間を{右端,左端}と保存しておく（普通と逆順に入れとく）
すると、lower_bound({x,-1})とすることで高速にxが属する区間が得られる。
結合する場合は、A[i]が属する区間の要素とB[i]が属する区間の要素とその間にある要素を全て消して、1つにまとめればいい。
まとめる処理はならしO(N)となるので、全体として間に合う。
setで区間を管理するテクはcodeforcesなどで割と出るので、練習しておこう。

int N, M, Q, D[101010], A[101010], B[101010], E[101010], S[101010], T[101010];
string ans[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> Q;
    rep(i, 0, M) cin >> D[i] >> A[i] >> B[i];
    rep(i, 0, Q) cin >> E[i] >> S[i] >> T[i];

    set<pair<int, int>> gr;
    rep(i, 0, N) gr.insert({ i + 1, i + 1 });

    vector<int> ele, ord;
    rep(i, 0, M) ele.push_back(i);
    sort(all(ele), [&](int a, int b) { return D[a] < D[b]; });
    rep(i, 0, Q) ord.push_back(i);
    sort(all(ord), [&](int a, int b) { return E[a] < E[b]; });

    int elei = 0;
    rep(_i, 0, Q) {
        int i = ord[_i];

        if (S[i] >= T[i]) {
            ans[i] = "Yes";
            continue;
        }

        while (elei < M) {
            int j = ele[elei];
            if (E[i] <= D[j]) break;

            int a = A[j];
            int b = B[j];

            auto itea = gr.lower_bound({ a, -1 });
            auto iteb = gr.lower_bound({ b, -1 });

            int l = itea->second;
            int r = iteb->first;

            iteb++;

            gr.erase(itea, iteb);
            gr.insert({ r, l });
            elei++;
        }

        auto itea = gr.lower_bound({ S[i], -1 });
        auto iteb = gr.lower_bound({ T[i], -1 });

        if (itea == iteb) ans[i] = "Yes";
        else ans[i] = "No";
    }

    rep(i, 0, Q) printf("%s\n", ans[i].c_str());
}