Submission #590299

#	Time	Username	Problem	Language	Result	Execution time	Memory
590299		Error42	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	481 ms	20436 KiB

event2

#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <optional>
#include <set>
#include <vector>

using namespace std;

using ll = long long;

#define int ll

struct range {
    ll l, r;
};

struct event {
    int id;
    ::range range;

    event() : id(-1), range{ -1, -1 } {}
    event(int id, ::range range) : id(id), range(range) {}
};

struct started_range {
    ll r;
    event start;

    ::range range() const {
        return { start.range.r, r };
    }

    explicit started_range(ll r) : r(r), start(-1, ::range{ -INT_MAX, -INT_MAX }) {}
    started_range(ll r, const event& start) : r(r), start(start) {}

    bool operator <(const started_range& other) const {
        return r < other.r;
    }
};

int sqrt_n;
vector<event> events;
event first;
vector<optional<event>> next_one;
vector<optional<event>> next_sqrt_n;

int max_events(const started_range& sr) {
    ll r = sr.r;
    const int after_id = sr.start.id;

    int ans = 0;

    int cur = after_id;

    if (cur == -1) {
        ans++;
        cur = first.id;
    }

    while (next_sqrt_n[cur] && next_sqrt_n[cur]->range.r <= r) {
        ans += sqrt_n;
        cur = next_sqrt_n[cur]->id;
    }

    while (next_one[cur] && next_one[cur]->range.r <= r) {
        ans++;
        cur = next_one[cur]->id;
    }

    return ans;
}

signed main() {
    int n, k;
    cin >> n >> k;

    events.resize(n);

    for (int i = 0; i < n; i++) {
        event& e = events[i];
        e.id = i;
        cin >> e.range.l >> e.range.r;
    }

    next_one.resize(n);

    {
        vector<event> l_rev_sorted = events;
        sort(l_rev_sorted.begin(), l_rev_sorted.end(), [](const event& a, const event& b) {
            return a.range.l > b.range.l;
            });

        vector<event> r_rev_sorted = events;
        sort(r_rev_sorted.begin(), r_rev_sorted.end(), [](const event& a, const event& b) {
            return a.range.r > b.range.r;
            });

        int r_min = -1;
        int l_idx = 0;

        for (const event& cur : r_rev_sorted) {
            while (l_idx < l_rev_sorted.size()
                && l_rev_sorted[l_idx].range.l >= cur.range.r) {

                if (r_min == - 1 || l_rev_sorted[l_idx].range.r < events[r_min].range.r)
                    r_min = l_rev_sorted[l_idx].id;
                l_idx++;
            }

            if (r_min != -1)
                next_one[cur.id] = events[r_min];
        }

        first = r_rev_sorted.back();
    }

    // does not need to be exact
    sqrt_n = int(sqrt(double(n)));

    next_sqrt_n.resize(n);

    for (int i = 0; i < n; i++) {
        int cur = i;

        for (int j = 0; j < sqrt_n && cur != -1; j++) {
            if (next_one[cur])
                cur = next_one[cur]->id;
            else
                cur = -1;
        }

        if (cur != -1)
            next_sqrt_n[i] = events[cur];
    }

    set<started_range> usable = { started_range(INT_MAX) };

    int cur_events = max_events(*usable.begin());

    if (cur_events < k) {
        cout << "-1\n";
        return 0;
    }

    vector<bool> in(n, false);

    for (const auto& tested : events) {
        auto usable_it = usable.lower_bound(started_range(tested.range.r));

        if (usable_it->range().l > tested.range.l)
            continue;

        int before_split = max_events(*usable_it);

        started_range split_l = *usable_it;
        split_l.r = tested.range.l;

        started_range split_r{ usable_it->r, tested };

        int after_split = max_events(split_l) + 1 + max_events(split_r);

        if (cur_events - before_split + after_split >= k) {
            in[tested.id] = true;

            usable.erase(*usable_it);
            usable.insert(split_l);
            usable.insert(split_r);
        }
    }

    vector<int> solution;

    for (int i = 0; solution.size() < k; i++)
        if (in[i])
            solution.push_back(i);

    for (const int x : solution)
        cout << x + 1 << "\n";
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:104:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             while (l_idx < l_rev_sorted.size()
      |                    ~~~~~~^~~~~~~~~~~~~~~~~~~~~
event2.cpp:175:37: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  175 |     for (int i = 0; solution.size() < k; i++)
      |                     ~~~~~~~~~~~~~~~~^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61