oj.uz

Submission #721562

# Submission time Handle Problem Language Result Execution time Memory
721562 2023-04-11T04:24:18 Z drdilyor Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 8320 KB 
#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 (s == e) {
            cout << "0\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 (found)cout << ans+1 << '\n';
        else cout << "impossible\n";
    }


    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1558 ms 8320 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Incorrect 4 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Incorrect 4 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Incorrect 4 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1564 ms 6444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1558 ms 8320 KB Time limit exceeded
3 Halted 0 ms 0 KB -