Submission #1231444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231444		omsincoconut	Event Hopping (BOI22_events)	C++17	10 / 100	1604 ms	589824 KiB

events

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

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

    int ord[N+1];
    iota(ord+1, ord+N+1, 1);
    sort(ord+1, ord+N+1, [&E, &S](int a, int b) {return (E[a] > E[b]) || (E[a] == E[b] && S[a] > S[b]);});

    int ans[N+1][N+1];
    priority_queue<pair<int, int>> pq[N+1];
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            while (!pq[j].empty() && S[pq[j].top().second] > E[ord[i]]) pq[j].pop();

            int val;
            if (ord[i] == j) val = 0;
            else val = (pq[j].empty() ? INF : -pq[j].top().first)+1;
            pq[j].emplace(-val, ord[i]);

            ans[ord[i]][j] = val;
            if (E[ord[i]] == E[j]) ans[ord[i]][j] = min(ans[ord[i]][j], 1);
        }
    }

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

        int val = ans[s][e];

        if (val > N) cout << "impossible\n";
        else cout << val << "\n";
    }


    return 0;
}

/*
5 2
1 3
2 4
4 7
7 9
3 7
1 4
3 2
*/

/*
8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8
*/

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