Submission #1098224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098224		rifat414141	Event Hopping (BOI22_events)	C++17	100 / 100	103 ms	28488 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);
// }
struct Seg
{
    int siz;
    vector<pair<int, int>> v;

    void init(int n)
    {
        siz = 1;
        while (siz < n)
            siz *= 2;
        v.assign(siz * 2, make_pair(INF, -1));
    }

    pair<int, int> merge(pair<int, int> x, pair<int, int> y)
    {
        pair<int, int> res;
        res.first = min(x.first, y.first);
        if (x.first == y.first)
            res.second = min(x.second, y.second);
        else if (res.first == x.first)
            res.second = x.second;
        else
            res.second = y.second;
        return res;
    }

    void set(int i, pair<int, int> p, int x, int lx, int rx)
    {
        if (rx - lx == 1)
        {
            v[x] = merge(p, v[x]);
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m)
            set(i, p, 2 * x + 1, lx, m);
        else
            set(i, p, 2 * x + 2, m, rx);
        v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
    }

    void set(int i, pair<int, int> p)
    {
        set(i, p, 0, 0, siz);
    }

    pair<int, int> range_mx(int l, int r, int x, int lx, int rx)
    {
        if (l >= rx || lx >= r)
            return make_pair(INF, -1);
        if (lx >= l && rx <= r)
            return v[x];
        int m = (lx + rx) / 2;
        return merge(range_mx(l, r, 2 * x + 1, lx, m), range_mx(l, r, 2 * x + 2, m, rx));
    }

    pair<int, int> range_mx(int l, int r)
    {
        return range_mx(l, r, 0, 0, siz);
    }
};
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], crr[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;
        crr[i] = v2[i].second.second;
    }
    // build(1, 1, n);
    Seg st;
    st.init(n + 1);
    for (int i = n - 1; i >= 0; i--)
    {
        st.set(i, make_pair(v2[i].second.first, i));
    }

    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] = (st.range_mx(it, i)).second;
        }
    }
    for (int j = 1; j < LOGN; ++j)
    {
        for (int i = 0; i < n; ++i)
        {
            if (j == 1)
                up[i][j] = up[par[i]][j - 1];
            else
                up[i][j] = up[up[i][j - 1]][j - 1];
            // 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--;
        int ogs = brr[s], oge = brr[e];
        int sl = v2[ogs].second.first, sr = v2[ogs].first;
        int el = v2[oge].second.first, er = v2[oge].first;
        if (ogs > oge)
        {
            if (sr >= el && sr <= er)
            {
                cout << 1 << endl;
                continue;
            }
            else
            {
                cout << "impossible" << endl;
                continue;
            }
        }
        int curr = oge;
        int ans = 0;
        int mn = sr;
        for (int i = LOGN - 1; i >= 0; --i)
        {
            if (v2[up[curr][i]].second.first > mn)
            {
                ans += (1 << i);
                curr = up[curr][i];
            }
        }
        if (v1[crr[curr]].first > mn)
        {
            ans++;
            curr = up[curr][0];
        }
        ans++;
        curr = up[curr][0];
        if (v1[crr[curr]].first > mn)
        {
            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;
}

Compilation message (stderr)

events.cpp: In function 'void solve()':
events.cpp:167:13: warning: unused variable 'sl' [-Wunused-variable]
  167 |         int sl = v2[ogs].second.first, sr = v2[ogs].first;
      |             ^~

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