Submission #573617

#	Time	Username	Problem	Language	Result	Execution time	Memory
573617		eecs	Event Hopping (BOI22_events)	C++17	10 / 100	1589 ms	1084 KiB

events

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;
int n, q;
array<int, 2> a[maxn];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1];
    }
    while (q--) {
        int s, t, ans = 0;
        cin >> s >> t;
        if (s == t) { cout << "0\n"; continue; }
        s = a[s][1];
        while (s < a[t][0]) {
            int mx = 0;
            for (int i = 1; i <= n; i++) {
                if (a[i][0] <= s && a[i][1] <= a[t][1]) mx = max(mx, a[i][1]);
            }
            if (mx <= s) break;
            s = mx, ans++;
        }
        if (a[t][0] <= s && s <= a[t][1]) cout << ans + 1 << "\n";
        else cout << "impossible\n";
    }
    return 0;
}

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