Submission #604363

#	Time	Username	Problem	Language	Result	Execution time	Memory
604363		Jomnoi	Event Hopping (BOI22_events)	C++17	0 / 100	36 ms	2156 KiB

events

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

const int MAX_N = 1e5 + 5;
const int MAX_M = 5005;
const int INF = 1e9 + 7;

int S[MAX_N], E[MAX_N];
int can_reach[MAX_M][MAX_M];
int dp[MAX_N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int N, Q;
    cin >> N >> Q;

    vector <pair <int, int>> event;
    for(int i = 1; i <= N; i++) {
        cin >> S[i] >> E[i];

        event.emplace_back(S[i], E[i]);
    }

    sort(event.begin(), event.end());

    if(N <= 1000 and Q <= 100) {
        while(Q--) {
            int s, e;
            cin >> s >> e;

            int ps = lower_bound(event.begin(), event.end(), make_pair(S[s], E[s])) - event.begin();
            int pe = lower_bound(event.begin(), event.end(), make_pair(S[e], E[e])) - event.begin();

            for(int i = 0; i < N; i++) {
                dp[i] = INF;
            }
            dp[ps] = 0;

            for(int i = ps; i <= pe; i++) {
                auto [si, ei] = event[i];
                for(int j = i + 1; j <= pe; j++) {
                    auto [sj, ej] = event[j];
                    if(sj <= ei and ei <= ej) {
                        dp[j] = min(dp[j], dp[i] + 1);
                    }
                }
            }
            
            if(dp[pe] == INF) {
                cout << "impossible\n";
            }
            else {
                cout << dp[pe] << '\n';
            }
        }
    }
    // else if(N <= 5000) {
    //     memset(can_reach, -1, sizeof(can_reach));

    //     for(int i = 1; i <= N; i++) {
    //         can_reach[id[i]][id[i]] = 0;
    //         priority_queue <pair <int, int>> pq;
    //         pq.emplace(0, id[i]);
    //         for(int j = i + 1; j <= N; j++) {
    //             while(!pq.empty() and E[pq.top().second] < S[id[j]]) {
    //                 pq.pop();
    //             }

    //             if(!pq.empty()) {
    //                 can_reach[id[i]][id[j]] = -pq.top().first + 1;
    //                 pq.emplace(-can_reach[id[i]][id[j]], id[j]);
    //             }
    //         }
    //     }

    //     while(Q--) {
    //         int s, e;
    //         cin >> s >> e;

    //         if(can_reach[s][e] == -1) {
    //             cout << "impossible\n";
    //         }
    //         else {
    //             cout << can_reach[s][e] << '\n';
    //         }
    //     }
    // }
    // else if(Q <= 100) {
    //     while(Q--) {
    //         int s, e;
    //         cin >> s >> e;

    //         dp[p[e]] = -1;
    //         dp[p[s]] = 0;
    //         priority_queue <pair <int, int>> pq;
    //         pq.emplace(0, p[s]);
    //         for(int i = p[s] + 1; i <= p[e]; i++) {
    //             while(!pq.empty() and E[pq.top().second] < S[id[i]]) {
    //                 pq.pop();
    //             }

    //             if(!pq.empty()) {
    //                 dp[id[i]] = -pq.top().first + 1;
    //                 pq.emplace(-dp[id[i]], id[i]);
    //             }
    //         }

    //         if(dp[p[e]] == -1) {
    //             cout << "impossible\n";
    //         }
    //         else {
    //             cout << dp[p[e]] << '\n';
    //         }
    //     }
    // }
    // else {
    //     while(Q--) {
    //         int s, e;
    //         cin >> s >> e;

    //         if(s == e) {
    //             cout << "0\n";
    //         }
    //         else if(S[p[e]] <= E[p[s]] and E[p[s]] <= E[p[e]]) {
    //             cout << "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