Submission #625242

#	Time	Username	Problem	Language	Result	Execution time	Memory
625242		Ooops_sorry	Event Hopping (BOI22_events)	C++14	100 / 100	356 ms	20352 KiB

events

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld double
#define ll long long

mt19937 rnd(51);

const int N = 2e5 + 10, INF = 1e9;
int po[20][N];
pair<int,int> t[4 * N];

void update(int v, int l, int r, int pos, pair<int,int> val) {
    if (l == r) {
        t[v] = min(t[v], val);
        return;
    }
    int m = (l + r) / 2;
    if (pos <= m) {
        update(2 * v, l, m, pos, val);
    } else {
        update(2 * v + 1, m + 1, r, pos, val);
    }
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}

pair<int,int> get(int v, int tl, int tr, int l, int r) {
    if (l > r) return {INF, INF};
    if (tl == l && tr == r) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return min(get(2 * v, tl, tm, l, min(r, tm)), get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i < 4 * N; i++) {
        t[i] = {INF, INF};
    }
    int n, q;
    cin >> n >> q;
    vector<int> s(n), e(n), u;
    for (int i = 0; i < n; i++) {
        cin >> s[i] >> e[i];
        u.pb(s[i]);
        u.pb(e[i]);
    }
    sort(u.begin(), u.end());
    u.erase(unique(u.begin(), u.end()), u.end());
    int sz = u.size();
    for (int i = 0; i < n; i++) {
        s[i] = lower_bound(u.begin(), u.end(), s[i]) - u.begin();
        e[i] = lower_bound(u.begin(), u.end(), e[i]) - u.begin();
        update(1, 0, sz - 1, e[i], {s[i], i});
    }
    for (int i = 0; i < n; i++) {
        po[0][i] = get(1, 0, sz - 1, s[i], e[i]).second;
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            po[i][j] = po[i - 1][po[i - 1][j]];
        }
    }
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (a == b) {
            cout << 0 << endl;
        } else if (e[a] > e[b]) {
            cout << "impossible" << endl;
        } else {
            if (s[b] <= e[a] && e[a] <= e[b]) {
                cout << 1 << endl;
                continue;
            }
            int cnt = 2;
            for (int j = 19; j >= 0; j--) {
                if (e[a] < s[po[j][b]]) {
                    b = po[j][b];
                    cnt += (1 << j);
                }
            }
            b = po[0][b];
            if (e[a] < s[b]) {
                cout << "impossible" << endl;
            } else {
                cout << cnt << endl;
            }
        }
    }
    return 0;
}

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