Submission #1098033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098033		rifat414141	Event Hopping (BOI22_events)	C++17	20 / 100	85 ms	30100 KiB

events

#include <bits/stdc++.h>
#define int long long int
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e18;
const int LOGN = 20;
int arr[N];
pair<int, int> segment_tree[4 * N];
int up[N][LOGN];
int par[N];
void build(int id, int l, int r)
{
    if (l == r)
    {
        segment_tree[id] = {arr[l - 1], l - 1};
        return;
    }
    int mid = (l + r) / 2;
    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);
    segment_tree[id] = min(segment_tree[2 * id], segment_tree[2 * id + 1]);
    return;
}
pair<int, int> range(int id, int l, int r, int L, int R)
{
    if (R < l || L > r)
    {
        return {INF, INF};
    }
    if (L <= l && r <= R)
    {
        return segment_tree[id];
    }
    int mid = (l + r) / 2;
    pair<int, int> x = range(2 * id, l, mid, L, R);
    pair<int, int> y = range(2 * id + 1, mid + 1, r, L, R);
    return min(x, y);
}
void solve()
{
    int n, q;
    cin >> n >> q;
    vector<pair<int, int>> v1;
    vector<pair<int, pair<int, int>>> v2;
    for (int i = 0; i < n; ++i)
    {
        int l, r;
        cin >> l >> r;
        v1.push_back({l, r});
        v2.push_back({r, {l, i}});
    }
    int brr[n];
    sort(v2.begin(), v2.end());
    for (int i = 0; i < n; ++i)
    {
        arr[i] = v2[i].second.first;
        brr[v2[i].second.second] = i;
    }
    build(1, 1, n);
    for (int i = 0; i < n; ++i)
    {
        pair<int, pair<int, int>> p = {v2[i].second.first, {-1, -1}};
        int it = lower_bound(v2.begin(), v2.end(), p) - v2.begin();
        // cout << v2[i].first << ' ' << it << endl;
        if (it == i)
        {
            up[i][0] = par[i] = i;
        }
        else
        {
            auto idx = range(1, 1, n, it + 1, i + 1);
            up[i][0] = par[i] = idx.second;
        }
    }
    for (int i = 1; i < LOGN; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    while (q--)
    {
        int s, e;
        cin >> s >> e;
        if (s == e)
        {
            cout << 0 << endl;
            continue;
        }
        s--, e--;
        s = brr[s], e = brr[e];
        int sl = v2[s].second.first, sr = v2[s].first;
        int el = v2[e].second.first, er = v2[e].first;
        if (s > e)
        {
            if (sl >= el && sr <= er)
            {
                cout << 1 << endl;
                continue;
            }
            else
            {
                cout << "impossible" << endl;
                continue;
            }
        }
        int curr = e;
        int ans = 0;
        for (int i = LOGN - 1; i >= 0; --i)
        {
            if (v2[up[curr][i]].first > sr)
            {
                ans += (1 << i);
                curr = up[curr][i];
            }
        }
        if (v2[up[curr][0]].first > sr)
        {
            ans++;
            curr = up[curr][0];
        }
        ans++;
        curr = up[curr][0];
        if (v2[curr].first > sr)
        {
            cout << "impossible" << endl;
            continue;
        }
        else
        {
            cout << ans << endl;
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("prime_subtractorization_input.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int t = 1;
    // cin >> t;
    for (int tt = 1; tt <= t; ++tt)
    {
        // cout << "Case #" << tt << ": ";
        solve();
    }

    return 0;
}

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