oj.uz

Submission #604354

# Submission time Handle Problem Language Result Execution time Memory
604354 2022-07-25T04:33:06 Z Jomnoi Event Hopping (BOI22_events) C++17
0 / 100
 44 ms 3556 KB 
#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';
            }
        }
    }
    else {
        while(Q--) {
            int s, e;
            cin >> s >> e;

            if(s == e) {
                cout << "0\n";
            }
            else if(S[id[e]] <= E[id[s]] and E[id[s]] <= E[id[e]]) {
                cout << "1\n";
            }
            else {
                cout << "impossible\n";
            }
        }
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 3556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -