Submission #588713

#	Time	Username	Problem	Language	Result	Execution time	Memory
588713		1zaid1	Event Hopping (BOI22_events)	C++17	0 / 100	1591 ms	1492 KiB

events

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30