Submission #694109

#	Time	Username	Problem	Language	Result	Execution time	Memory
694109		finn__	Event Hopping (BOI22_events)	C++17	100 / 100	241 ms	32324 KiB

events

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

typedef pair<int64_t, int64_t> Interval;

struct SegmentTree
{
    vector<pair<int64_t, unsigned>> t;
    size_t l;

    SegmentTree(size_t n)
    {
        l = 1U << (32U - __builtin_clz(n));
        t = vector<pair<int64_t, unsigned>>(2 * l, make_pair(INT64_MAX, UINT_MAX));
    }

    void update(size_t i, pair<int64_t, unsigned> const &x)
    {
        i += l;
        t[i] = min(t[i], x);
        while (i >>= 1)
            t[i] = min(t[2 * i], t[2 * i + 1]);
    }

    pair<int64_t, unsigned> range_min(size_t i, size_t j)
    {
        i += l, j += l;
        pair<int64_t, unsigned> x = make_pair(INT64_MAX, UINT_MAX);

        while (i <= j)
        {
            if (i & 1)
                x = min(x, t[i++]);
            if (!(j & 1))
                x = min(x, t[j--]);
            i >>= 1;
            j >>= 1;
        }

        return x;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, q;
    cin >> n >> q;

    vector<Interval> intervals(n);
    vector<int64_t> coords;
    for (Interval &z : intervals)
    {
        cin >> z.first >> z.second;
        coords.push_back(z.first);
        coords.push_back(z.second);
    }
    sort(coords.begin(), coords.end());
    coords.resize(unique(coords.begin(), coords.end()) - coords.begin());

    for (Interval &x : intervals)
    {
        x.first = lower_bound(coords.begin(), coords.end(), x.first) - coords.begin();
        x.second = lower_bound(coords.begin(), coords.end(), x.second) - coords.begin();
    }

    SegmentTree tree(coords.size());
    vector<vector<unsigned>> pre(n);

    for (size_t i = 0; i < n; i++)
        tree.update(intervals[i].second, make_pair(intervals[i].first, i));

    for (size_t i = 0; i < n; i++)
    {
        pre[i].push_back(
            tree.range_min(intervals[i].first, intervals[i].second).second);
    }

    for (size_t j = 1; j <= 32U - __builtin_clz(n); j++)
    {
        for (size_t i = 0; i < n; i++)
        {
            pre[i].push_back(pre[pre[i][j - 1]][j - 1]);
        }
    }

    while (q--)
    {
        unsigned u, v;
        cin >> u >> v;
        u--, v--;

        if (u == v)
        {
            cout << "0\n";
            continue;
        }

        if (intervals[u].second > intervals[v].second)
        {
            cout << "impossible\n";
            continue;
        }

        if (intervals[v].first <= intervals[u].second &&
            intervals[u].second <= intervals[v].second)
        {
            cout << "1\n";
            continue;
        }

        unsigned d = 0;
        for (unsigned i = pre[v].size() - 1; i < pre[v].size(); i--)
        {
            if (intervals[pre[v][i]].first > intervals[u].second)
                v = pre[v][i], d += 1U << i;
        }

        if (d <= n)
            cout << d + 2 << '\n';
        else
            cout << "impossible\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