Submission #602670

#	Time	Username	Problem	Language	Result	Execution time	Memory
602670		shrimb	Event Hopping (BOI22_events)	C++17	20 / 100	143 ms	28336 KiB

events

#include"bits/stdc++.h"
using namespace std;
const int maxn = 200001;
const int N = exp2(ceil(log2(maxn)));
pair<int,int> seg[2 * N], Val;
int Left, Right, Pos;
pair<int,int> Query (int l = 1, int r = N, int ind = 1) {
    if (l > Right || r < Left) return pair<int,int>{-1, -1};
    if (l >= Left and r <= Right) return seg[ind];
    int m = (l + r) / 2;
    return max(Query(l, m, ind * 2), Query(m + 1, r, ind * 2 + 1));
}
void Update () {
    int ind = N + Pos - 1;
    seg[ind] = Val;
    while (ind /= 2) seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
}
int Sparse[maxn][22];
signed main () {
    cin.tie(0) -> sync_with_stdio(0);
    for (auto& [i, j] : seg) i = j = -1;
    memset(Sparse, -1, sizeof Sparse);
    int n, q;
    cin >> n >> q;
    pair<int,int> a[n];

    vector<int*> v;
    for (auto& [i, j] : a) {
        cin >> i >> j;
        v.push_back(&i);
        v.push_back(&j);
    }
    sort(v.begin(), v.end(), [](int*i,int*j){return *i<*j;});
    int prev = -1;
    int id = 0;
    for (auto & i : v) {
        if (*i != prev) id++;
        prev=*i;
        *i = id;
    }
    int P[n + 1];
    for (int i = 1 ; i <= n ; i++) P[i] = i - 1;
    sort(P + 1, P + 1 + n, [&](int i, int j){return a[i] < a[j];});
    int conv[n + 1];
    for (int i = 1 ; i <= n ; i++) conv[P[i] + 1] = i - 1;
    sort(a, a + n);
    // cerr << "conv: ";
    // for (int i = 1 ; i <= n ; i++) cerr << conv[i] << " ";
    // cerr << "\n";
    Left = 1;
    for (int i = n - 1 ; i >= 0 ; i--) {
        if (i < n - 1) {
            Right = a[i].second;
            Sparse[i][0] = Query().second;
        }
        Pos = a[i].first;
        Val = {a[i].second, i};
        Update();
    }
    for (int j = 1 ; j < 20 ; j++) {
        for (int i = 0 ; i < n ; i++) {
            if (Sparse[i][j-1] != -1) Sparse[i][j] = Sparse[Sparse[i][j-1]][j-1];
            // cerr << i << " " << j << ": " << Sparse[i][j] << endl;
        }
    }
    // cout << "~~~~~~~~~~~\n";
    // for (int i = 0 ; i < n ; i++) {
    //     cout << a[i].first << " " << a[i].second << endl;
    // }
    // // cout << "~~~~~~~~~~~~\n";
    // for (int i = 0 ; i < n ; i++) {
    //     cout << Sparse[i][0] << " ";
    // }
    // cout << '\n';
    while (q--) {
        int i, j;
        cin >> i >> j;
        // cerr << "conv: " << i << " " << j << '\n';
        i = conv[i], j = conv[j];
        // cerr << "conv: " << i << " " << j << '\n';
        if (i == j) {
            cout << 0 << endl;
            continue;
        }
        if (a[j].second < a[i].second) {
            cout << "impossible\n";
            continue;
        }
        if (a[j].first <= a[i].second and a[j].second >= a[i].second) {
            cout << 1 << '\n';
            continue;
        }
        int cnt = 0;
        for (int k = 19 ; k >= 0 ; k--) {
            if (Sparse[i][k] != -1) {
                if (a[Sparse[i][k]].second < a[j].first) {
                    // cerr << Sparse[i][k] << endl;
                    // cerr << i << " " << k << endl;
                    cnt += (1 << k);
                    i = Sparse[i][k];
                }
            }
        }
        // cerr << "debug: " << i << " " << cnt << endl;
        if (Sparse[i][0] != -1 and a[Sparse[i][0]].second >= a[j].first and a[Sparse[i][0]].second <= a[j].second) {
            cout << cnt + 2 - (Sparse[i][0] == j) << '\n';

        } else {
            cout << "impossible\n";
        }
    }
}

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