제출 #721556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721556		drdilyor	Event Hopping (BOI22_events)	C++17	0 / 100	1538 ms	8096 KiB

events

#include<bits/stdc++.h>
using namespace std;
using ll = long long;


const int inf = 1e9 + 1e5;

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> ev(n), og;
    for (auto& [s, e] : ev) cin >> s >> e;
    og = ev;
    sort(ev.begin(), ev.end());
    ev.emplace_back(inf, inf);

    while (m--) {
        int s, e;
        cin >> s >> e;
        s--;e--;
        multiset<int,greater<>> right;
        int sr = og[s].second;
        int ans{}, found{};
        if (og[e].second <= og[s].first) {
            cout << "impossible\n";
            continue;
        }
        if (max(og[s].first, og[e].first) < min(og[s].second, og[e].second)) {
            cout << "1\n";
            continue;
        }
        for (auto [l, r] : ev) {
            if (r < sr) continue;
            if (sr < l) {
                if (og[e].first <= sr && sr <= og[e].second) {
                    found = 1;
                    break;
                }
                ans++;
                sr = *right.begin();
            }
            right.insert(r);
        }
        if (og[e].first <= sr && sr <= og[e].second) {
            found = 1;
        }
        if (found)cout << ans+1 << '\n';
        else cout << "impossible\n";
    }


    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30