Submission #1103111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103111		MateiKing80	Event Hopping (BOI22_events)	C++14	100 / 100	124 ms	22348 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define fr first
#define sc second

const int B = 17;
int n;

struct Rmq
{
    int rmq[B][100005];
    void build(int arr[])
    {
        for(int i = 1; i <= n; i ++)
            rmq[0][i] = arr[i];
        for(int p = 0; p + 1 < B; p ++)
            for(int i = 1; i <= n - (1 << p); i ++)
                rmq[p + 1][i] = min(rmq[p][i], rmq[p][i + (1 << p)]);
    }
    int query(int l, int r)
    {
        int p = __lg(r - l + 1);
        return min(rmq[p][l], rmq[p][r - (1 << p) + 1]);
    }
} ds;

int q, rk[100005], ord[100005], lift[20][100005], lst[100005], ans[100005], start[100005];
pii p[100005], rng[100005];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i ++)
        cin >> p[i].fr >> p[i].sc;
    for(int i = 1; i <= n; i ++)
        rk[i] = i;
    sort(rk + 1, rk + 1 + n, [&](int i, int j)
    {
        return p[i].sc < p[j].sc;
    });
    for(int i = 1; i <= n; i ++)
        ord[rk[i]] = i;
    sort(p + 1, p + 1 + n, [&](pii i, pii j)
    {
        return i.sc < j.sc;
    });

    for(int i = 1; i <= n; i ++)
        lift[0][i] = lower_bound(p + 1, p + 1 + n, pii(0, p[i].fr), [](pii i, pii j)
                                                                    {
                                                                        return i.sc < j.sc;
                                                                    }) - p;
    for(int i = 1; i <= n; i ++)
        lst[i] = upper_bound(p + 1, p + 1 + n, pii(0, p[i].sc), [](pii i, pii j)
                                                                {
                                                                    return i.sc < j.sc;
                                                                }) - p - 1;
    for(int p = 0; p + 1 < B; p ++)
    {
        ds.build(lift[p]);
        for(int i = 1; i <= n; i ++)
            lift[p + 1][i] = ds.query(lift[p][i], lst[i]);
    }

    for(int i = 1; i <= q; i ++)
    {
        int u, v;
        cin >> u >> v;
        if(u == v)
            ans[i] = -1;
        start[i] = ord[u];
        rng[i] = pii(ord[v], ord[v]);
    }
    for(int p = B - 1; p >= 0; p --)
    {
        ds.build(lift[p]);
        for(int i = 1; i <= q; i ++)
        {
            pii nrange = pii(ds.query(rng[i].fr, rng[i].sc), lst[rng[i].sc]);
            if(start[i] < nrange.fr || nrange.sc < start[i])
            {
                ans[i] += (1 << p);
                rng[i] = nrange;
            }
        }
    }
    for(int i = 1; i <= q; i ++)
        if(ans[i] >= n)
            cout << "impossible\n";
        else
            cout << ans[i] + 1 << '\n';
}

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