Submission #1098199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098199		rifat414141	Event Hopping (BOI22_events)	C++17	100 / 100	90 ms	17728 KiB

events

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

#define ll long long
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define all(x) x.begin(), x.end()
#define vf first
#define vs second
const int mod = 998244353;

const int MX = 1000000005;
const int L = 20;

struct Seg
{
    int siz;
    vector<pair<int, int>> v;

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

    pair<int, int> merge(pair<int, int> x, pair<int, int> y)
    {
        pair<int, int> res;
        res.vf = min(x.vf, y.vf);
        if (x.vf == y.vf)
            res.vs = min(x.vs, y.vs);
        else if (res.vf == x.vf)
            res.vs = x.vs;
        else
            res.vs = y.vs;
        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 mp(MX, -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>> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i].vf >> v[i].vs;
    }

    // positions acocrding to sorted e

    vector<pair<int, pair<int, int>>> e_sort;
    // vector<pair<int,pair<int,int>>> rev;

    for (int i = 0; i < n; i++)
    {
        e_sort.pb(mp(v[i].vs, mp(v[i].vf, i)));
    }
    sort(all(e_sort));
    // rev = e_sort;
    // reverse(all(rev));
    int pos[n], rev[n];
    for (int i = 0; i < n; i++)
    {
        pos[e_sort[i].vs.vs] = i;
        rev[i] = e_sort[i].vs.vs;
    }

    // segtree

    Seg st;
    st.init(n + 1);
    for (int i = n - 1; i >= 0; i--)
    {
        st.set(i, mp(e_sort[i].vs.vf, i));
    }

    // binary lifting

    int up[n][L];
    int p[n];
    for (int i = 0; i < n; i++)
    {
        pair<int, pair<int, int>> tp = mp(e_sort[i].vs.vf, mp(-1, -1));
        int left = (lower_bound(all(e_sort), tp) - e_sort.begin());
        if (left == i)
            up[i][0] = p[i] = i;
        else
        {
            p[i] = st.range_mx(left, i).vs;
            // cout << left << ' ' << st.range_mx(left,i).vf << ' ' << p[i] << '\n';
            up[i][0] = p[i];
        }
    }
    for (int j = 1; j < L; j++)
    {
        for (int i = 0; i < n; i++)
        {
            // if (j == 1)
            //     up[i][j] = up[p[i]][j - 1];
            // else
                up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }

    // answering the queries

    while (q--)
    {
        int s, e;
        cin >> s >> e;
        s--;
        e--;
        if (s == e)
        {
            cout << 0 << '\n';
            continue;
        }
        int ogs = pos[s], oge = pos[e];
        if (ogs > oge)
        {
            if (v[s].vs >= v[e].vf && v[s].vs <= v[e].vs)
            {
                cout << 1 << '\n';
                continue;
            }
            else
            {
                cout << "impossible\n";
                continue;
            }
        }
        int i = oge;
        int mn = v[s].vs;
        int ans = 0;
        for (int j = L - 1; j >= 0; j--)
        {
            if (v[rev[up[i][j]]].vf > mn)
            {
                ans += (1 << j);
                i = up[i][j];
            }
        }
        if (v[rev[i]].vf > mn)
        {
            i = up[i][0];
            ans++;
        }
        ans++;
        i = up[i][0];
        if (v[rev[i]].vf > mn)
            cout << "impossible\n";
        else
            cout << ans << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // int t;cin >> t;
    // while(t--)
    solve();
    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