Submission #604299

#	Time	Username	Problem	Language	Result	Execution time	Memory
604299		Jomnoi	Event Hopping (BOI22_events)	C++17	0 / 100	29 ms	3556 KiB

events

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

const int MAX_N = 1e5 + 5;
const int MAX_M = 5005;

int S[MAX_N], E[MAX_N], id[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;

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

        id[i] = i;
    }

    sort(id + 1, id + N + 1, [&](const int &a, const int &b) {
        return S[a] < S[b];
    });

    if(N <= 5000 and false) {
        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[id[e]] = -1;
            dp[id[s]] = 0;
            priority_queue <pair <int, int>> pq;
            pq.emplace(0, id[s]);
            for(int i = id[s] + 1; i <= id[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[id[e]] == -1) {
                cout << "impossible\n";
            }
            else {
                cout << dp[id[e]] << '\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