Submission #579629

#	Time	Username	Problem	Language	Result	Execution time	Memory
579629		Elias	Event Hopping (BOI22_events)	C++17	10 / 100	1591 ms	11324 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;

    bool operator<(Range other)
    {
        return tuple<int, int, int>{s, e, i} < tuple<int, int, int>{other.s, other.e, other.i};
    }
};

int n, q;

vector<Range> ranges, sR;

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;
    }

    sR = ranges;

    sort(sR.begin(), sR.end());

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

        set<pair<int, int>> ongoing;

        int t = ranges[s].e;
        int index = s;
        int i = 0;

        int cost = 0;

        while (true)
        {
            if (index == e || index == LLONG_MAX)
            {
                cout << cost << "\n";
                goto next;
            }

            while (i < n && sR[i].s <= t)
            {
                if (sR[i].e >= t)
                    ongoing.insert({sR[i].e, (sR[i].i == e ? LLONG_MAX : sR[i].i)});
                i++;
            }

            while (ongoing.size() && prev(ongoing.end())->first > ranges[e].e) // remove invalid ones -> where you would jump too far
                ongoing.erase(prev(ongoing.end()));

            if (!ongoing.size())
            {
                cout << "impossible\n";
                goto next;
            }

            cost++;

            t = prev(ongoing.end())->first;
            index = prev(ongoing.end())->second;
            ongoing = set<pair<int, int>>();
        }

    next:
        continue;
    }
}

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