Submission #929897

#	Time	Username	Problem	Language	Result	Execution time	Memory
929897		Pannda	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	386 ms	49388 KiB

event2

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

const int INF = 1e9 + 12345;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<array<int, 2>> a(n);
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        a[i] = {l, r};
    }

    auto [next, prev] = [](int n, vector<array<int, 2>> a) {
        int log = 32 - __builtin_clz(n);
        vector<vector<int>> next(n, vector<int>(log, -1));
        vector<vector<int>> prev(n, vector<int>(log, -1));
        vector<array<int, 3>> events;
        for (int i = 0; i < n; i++) {
            events.push_back({ a[i][0], +1, i });
            events.push_back({ a[i][1], -1, i });
        }
        sort(events.begin(), events.end());
        priority_queue<array<int, 2>, vector<array<int, 2>>, less<>> mx_pq;
        for (auto [x, type, i] : events) {
            if (type == -1) {
                mx_pq.push({ a[i][0], i });
            } else {
                prev[i][0] = mx_pq.empty() ? -1 : mx_pq.top()[1];
            }
        }
        reverse(events.begin(), events.end());
        priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> mn_pq;
        for (auto [x, type, i] : events) {
            if (type == +1) {
                mn_pq.push({ a[i][1], i });
            } else {
                next[i][0] = mn_pq.empty() ? -1 : mn_pq.top()[1];
            }
        }
        for (int t = 1; t < log; t++) {
            for (int i = 0; i < n; i++) {
                next[i][t] = next[i][t - 1] == -1 ? -1 : next[next[i][t - 1]][t - 1];
                prev[i][t] = prev[i][t - 1] == -1 ? -1 : prev[prev[i][t - 1]][t - 1];
            }
        }
        return make_pair(next, prev);
    }(n, a);

    auto forward_lift = [&](int i, int bound) {
        int lifted = 0;
        for (int t = next[i].size() - 1; t >= 0; t--) {
            int j = next[i][t];
            if (j != -1 && a[j][1] <= bound) {
                i = j;
                lifted += 1 << t;
            }
        }
        return lifted;
    };

    auto backward_lift = [&](int i, int bound) {
        int lifted = 0;
        for (int t = prev[i].size() - 1; t >= 0; t--) {
            int j = prev[i][t];
            if (j != -1 && bound <= a[j][0]) {
                i = j;
                lifted += 1 << t;
            }
        }
        return lifted;
    };

    set<array<int, 2>> cut = { {-INF, -1}, {INF, -1} };
    auto intersect = [&](int i, int j) {
        if (i == -1 || j == -1) return false;
        if (a[i] == a[j]) return true;
        return (a[j][0] < a[i][0] && a[i][0] < a[j][1]) || (a[i][0] < a[j][0] && a[j][0] < a[i][1]) || (a[j][0] < a[i][1] && a[i][1] < a[j][1]) || (a[i][0] < a[j][1] && a[j][1] < a[i][1]);
    };

    vector<int> key;
    int cur;
    for (int i = 0; i < n; i++) {
        auto [m1, im1] = *cut.lower_bound(array<int, 2>{a[i][0], -INF});
        auto [m2, im2] = *cut.upper_bound(array<int, 2>{a[i][0], INF});
        auto [l, il] = *--cut.upper_bound(array<int, 2>{a[i][0], INF});
        auto [r, ir] = *cut.lower_bound(array<int, 2>{a[i][1], -INF});
        if (intersect(i, im1) || intersect(i, im2) || intersect(i, il) || intersect(i, ir)) {
            continue;
        }
        int cur_try;
        if (il == -1 && ir == -1) {
            cur_try = forward_lift(i, INF) + backward_lift(i, -INF) + 1;
        } else if (il == -1) {
            cur_try = cur - backward_lift(ir, -INF) + forward_lift(i, r) + backward_lift(i, -INF) + 1;
        } else if (ir == -1) {
            cur_try = cur - forward_lift(il, INF) + forward_lift(i, INF) + backward_lift(i, l) + 1;
        } else {
            cur_try = cur - forward_lift(il, r) + forward_lift(i, r) + backward_lift(i, l) + 1;
        }
        if (cur_try < k) continue;
        cur = cur_try;
        key.push_back(i);
        cut.insert({a[i][0], i});
        cut.insert({a[i][1], i});
    }

    if (key.empty()) {
        cout << -1 << '\n';
    } else {
        assert(key.size() >= k);
        key.resize(k);
        for (int i : key) {
            cout << i + 1 << '\n';
        }
    }
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from event2.cpp:1:
event2.cpp: In function 'int main()':
event2.cpp:117:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |         assert(key.size() >= k);
      |                ~~~~~~~~~~~^~~~
event2.cpp:105:27: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |             cur_try = cur - forward_lift(il, r) + forward_lift(i, r) + backward_lift(i, l) + 1;
      |                       ~~~~^~~~~~~~~~~~~~~~~~~~~

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