Submission #579664

#	Time	Username	Problem	Language	Result	Execution time	Memory
579664		Elias	Event Hopping (BOI22_events)	C++17	0 / 100	106 ms	42940 KiB

events

#include <bits/stdc++.h>

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#endif

using namespace std;

#define int int64_t

template <class T>
istream &operator>>(istream &in, vector<T> &v)
{
    for (T &x : v)
        in >> x;
    return in;
}

struct Range
{
    int s, e, i, d;

    bool operator<(Range other) const
    {
        if (d == false)
            return tuple<int, int, int>{e, s, i} < tuple<int, int, int>{other.e, other.s, other.i};
        else
            return tuple<int, int, int>{s, e, i} < tuple<int, int, int>{other.s, other.e, other.i};
    }
};

int n, q;

vector<Range> ranges, sE, sB;

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

    cin >> n >> q;

    ranges = vector<Range>(n);

    for (int i = 0; i < n; i++)
    {
        cin >> ranges[i].s >> ranges[i].e;
        ranges[i].i = i;
    }

    sE = sB = ranges;

    for (int i = 0; i < n; i++)
        sB[i].d = 1;

    sort(sE.begin(), sE.end());
    sort(sB.begin(), sB.end());

    vector<vector<int>> next(20, vector<int>(n, -1));
    vector<vector<int>> pre(20, vector<int>(n, -1));

    set<Range> reachable;

    for (int j = n - 1; j >= 0; j--)
    {
        auto [s, e, i, d] = sE[j];

        while (reachable.size() && prev(reachable.end())->s > e)
            reachable.erase(prev(reachable.end()));

        if (reachable.size())
            next[0][j] = prev(reachable.end())->i;

        reachable.insert({s, e, i, d});
    }

    // for (int i = 1; i )

    for (int k = 1; k < 20; k++)
        for (int i = 0; i < n; i++)
        {
            if (next[k - 1][i] != -1)
                next[k][i] = next[k - 1][next[k - 1][i]];
        }

    while (q--)
    {
        int s, e;
        cin >> s >> e;

        s--, e--;

        if (s == e)
        {
            cout << "0\n";
            continue;
        }

        int count = 0;

        for (int k = 19; k >= 0; k--)
        {
            if (next[k][s] != -1 && ranges[next[k][s]].e < ranges[e].s)
            {
                s = next[k][s];
                count += pow(2, k);
            }
        }

        int cnt = 0;

        while (cnt < 100 && s != -1 && ranges[s].e < ranges[e].s)
        {
            s = next[0][s];
            count++;
            cnt++;
        }

        if (s == -1 || ranges[s].e > ranges[e].e)
        {
            cout << "impossible\n";
        }
        else
        {
            cout << count + 1 << "\n";
        }
    }
}

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