Submission #599163

#	Time	Username	Problem	Language	Result	Execution time	Memory
599163		SlavicG	Event Hopping (BOI22_events)	C++17	100 / 100	466 ms	43740 KiB

events

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

const int N = 1e6 + 10, K = 23;
int l[N], r[N], n, q;
int jump[N][K];
pair<int, int> t[4 * N];
void modif(int i, int l, int r, int pos, pair<int, int> x) {
    if(l > pos || r < pos) return;
    if(l == pos && r == pos) {
        t[i] = min(t[i], x);
        return;
    }
    int mid = l + r >> 1;
    modif(2 * i, l, mid, pos, x);
    modif(2 * i + 1, mid + 1, r, pos, x);
    t[i] = min(t[2 * i], t[2 * i + 1]);
}
pair<int, int> query(int i, int l, int r, int tl, int tr) {
    if(l > tr || r < tl) return {INT_MAX, -1};
    if(l >= tl && r <= tr) return t[i];
    int mid = l + r >> 1;
    return min(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr));
}

int main() {
    for(int i = 0; i < 4 * N; ++i) t[i] = {INT_MAX, -1};
    vector<int> v;
    cin >> n >> q;
    for(int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
        v.push_back(l[i]);
        v.push_back(r[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(int i = 0; i < n; ++i) {
        l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin();
        r[i] = lower_bound(v.begin(), v.end(), r[i]) - v.begin();

        modif(1, 0, N - 1, r[i], make_pair(l[i], i));
    }
    for(int i = 0; i < n; ++i) {
        jump[i][0] = query(1, 0, N - 1, l[i], r[i]).second;
    }
    for(int j = 1; j < K; ++j) {
        for(int i = 0; i < n; ++i) {
            jump[i][j] = jump[jump[i][j - 1]][j - 1];
        }
    }

    while(q--) {
        int a, b; cin >> a >> b; --a, --b;
        if(a == b) {
            cout << "0\n";
            continue;
        }
        if(r[a] > r[b]) {
            cout << "impossible\n";
            continue;
        }
        if(r[a] >= l[b]) {
            cout << "1\n";
            continue;
        }
        int ans = 0;
        for(int j = K - 1; j >= 0; --j) {
            if(l[jump[b][j]] > r[a]) {
                b = jump[b][j];
                ans += (1 << j);
            }
        }
        ans += 2;
        b = jump[b][0];
        if(l[b] > r[a]) {
            cout << "impossible\n";
            continue;
        }
        cout << ans << "\n";
    }
}

Compilation message (stderr)

events.cpp: In function 'void modif(int, int, int, int, std::pair<int, int>)':
events.cpp:14:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |     int mid = l + r >> 1;
      |               ~~^~~
events.cpp: In function 'std::pair<int, int> query(int, int, int, int, int)':
events.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int mid = l + r >> 1;
      |               ~~^~~

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