oj.uz

Submission #588712

# Submission time Handle Problem Language Result Execution time Memory
588712 2022-07-03T22:29:04 Z 1zaid1 Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 1492 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int M = 1e4+2;
struct rng {int l, r, i;};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, q;
    cin >> n >> q;

    vector<rng> v(n);
    for (auto &[l, r, i]:v) cin >> l >> r;
    for (int i = 0; i < n; i++) v[i].i = i;

    bitset<100005> vis;
    while (q--) {
        int a, b;
        cin >> a >> b; a--; b--;
        if (a == b) {
            cout << 0 << endl;
            continue;
        }

        vis[b] = 1;
        int ans = 0;
        rng cr = v[b];
        while (true) {
            // cout << q << "I: "<< cr.i+1 << endl;
            rng tmp;
            bool ch = 0;
            int mn = INT_MAX;
            for (auto [l, r, i]:v) {
                if (!vis[i]) {
                    if (cr.l <= r && r <= cr.r) {
                        if (i == a) {
                            ans++;
                            break;
                        }

                        if (l < mn) {
                            ch = true;
                            tmp = {l, r, i};
                            mn = l;
                        }
                    }
                }
            }

            if (!ch) break;
            ans++;
            cr = tmp;
            vis[cr.i] = 1;
        } vis = 0;

        if (cr.l <= v[a].r && v[a].r <= cr.r) {
            cout << ans << endl;
        } else {
            cout << "Impossible" << endl;
        }
    }
    
    return 0;
}
/*
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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 212 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 212 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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