結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
ユーザー InTheBloomInTheBloom
提出日時 2024-02-23 22:13:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 230 ms / 2,500 ms
コード長 1,359 bytes
コンパイル時間 1,487 ms
コンパイル使用メモリ 127,980 KB
実行使用メモリ 12,256 KB
最終ジャッジ日時 2024-09-29 06:58:13
合計ジャッジ時間 8,490 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;

int main () {
    int N, A; cin >> N >> A;
    vector<int> X(N);
    for (int i = 0; i < N; i++) cin >> X[i];

    int T; cin >> T;

    enum ElementType {
        sound_begin,
        sound_end,
        person,
    };

    vector<tuple<int, int, int>> events(2*T + N);
    for (int t = 0; t < T; t++) {
        int L, R; cin >> L >> R;
        events[t] = make_tuple(L, t+1, sound_begin);
        events[T+t] = make_tuple(R+1, t+1, sound_end);
    }

    for (int i = 0; i < N; i++) events[2*T + i] = make_tuple(X[i], i, person);

    sort(events.begin(), events.end(),
            [](tuple<int, int, int> x, tuple<int, int, int> y) {
            if (get<0>(x) != get<0>(y)) return get<0>(x) < get<0>(y);
            if (get<2>(x) == person) return false;
            if (get<2>(y) == person) return true;
            return true; });

    vector<int> ans(N, -1);

    map<int, int> mp;

    for (auto& e : events) {
        if (get<2>(e) == person) {
            if (!mp.empty()) ans[get<1>(e)] = mp.rbegin()->first;
        }

        if (get<2>(e) == sound_begin) {
            mp[get<1>(e)] = 0;
        }

        if (get<2>(e) == sound_end) {
            mp.erase(get<1>(e));
        }
    }

    for (auto& v : ans) cout << v << "\n";
}
0