Submission #726132

#	Time	Username	Problem	Language	Result	Execution time	Memory
726132		piOOE	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	142 ms	10936 KiB

event2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

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

    vector<array<int, 2>> a(n);

    vector<int> yy(2 * n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i][0] >> a[i][1];
        a[i][1] -= 1;
        yy[i * 2] = a[i][0];
        yy[i * 2 + 1] = a[i][1];
    }

    sort(yy.begin(), yy.end());
    yy.resize(unique(yy.begin(), yy.end()) - yy.begin());

    const int m = yy.size();

    for (auto &[l, r] : a) {
        l = lower_bound(yy.begin(), yy.end(), l) - yy.begin();
        r = lower_bound(yy.begin(), yy.end(), r) - yy.begin();
    }

    vector<array<int, 3>> s(n);
    vector<int> inv(n);

    for (int i = 0; i < n; ++i) {
        s[i] = {a[i][1], i, a[i][0]};
    }

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

    for (int i = 0; i < n; ++i) {
        inv[s[i][1]] = i;
    }

    a.push_back({m + 1, m + 1});
    s.push_back({m + 1, n, m + 1});

    vector<int> par(n + 1, n), depth(n + 1), jump(n + 1, n), dp(m, n);
    for (int i = n - 1; i >= 0; --i) {
        par[i] = par[i + 1];
        if (i + 1 < n) {
            for (int t = s[i][0] + 1; t <= s[i + 1][0]; ++t) {
                par[i] = min(par[i], dp[t]);
            }
        }
        dp[s[i][2]] = i;

        depth[i] = depth[par[i]] + 1;
        int p = jump[par[i]], pp = jump[p];
        if (depth[pp] - depth[p] == depth[p] - depth[par[i]]) {
            jump[i] = pp;
        } else {
            jump[i] = par[i];
        }
    }

    auto rangeQuery = [&](int l, int r) {
        l = max(l, 0);
        int ans = depth[l];
        while (l < n && s[l][0] < s[r][2]) {
            if (jump[l] < n && s[jump[l]][0] < s[r][2]) {
                l = jump[l];
            } else {
                l = par[l];
            }
        }
        ans -= depth[l];
        return ans;
    };

    int best = rangeQuery(0, n);

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

    set<int> alive;

    for (int i = 0; i < n && alive.size() < k; ++i) {
        int p = inv[i];
        auto it = alive.lower_bound(p);
        int r = it == alive.end() ? n : *it;
        int l = it == alive.begin() ? -1 : *prev(it);

        if (r != n && s[p][0] >= s[r][2] || l != -1 && s[l][0] >= a[i][0]) {
            continue;
        }

        int now = best - rangeQuery(l, r) + rangeQuery(l, p) + rangeQuery(p, r);
        if (now < k) {
            continue;
        }

        best = now;
        alive.insert(p);

        cout << i + 1 << "\n";
    }

    return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:92:43: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |     for (int i = 0; i < n && alive.size() < k; ++i) {
      |                              ~~~~~~~~~~~~~^~~
event2.cpp:98:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   98 |         if (r != n && s[p][0] >= s[r][2] || l != -1 && s[l][0] >= a[i][0]) {

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