Submission #726116

#	Time	Username	Problem	Language	Result	Execution time	Memory
726116		piOOE	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	111 ms	20968 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, 2>> s(n);
    vector<int> inv(n);

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

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

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

    vector<int> mn(2 * m, n);

    auto modify = [&](int x, int i) {
        for (mn[x += m] = i; x >>= 1; ) {
            mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
        }
    };

    auto rangeMin = [&](int l, int r) {
        int ans = n;
        for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ans = min(ans, mn[l++]);
            if (r & 1) ans = min(ans, mn[--r]);
        }
        return ans;
    };

    vector<int> par(n + 1, n), depth(n + 1), jump(n + 1, n);

    for (int i = n - 1; i >= 0; --i) {
        par[i] = rangeMin(s[i][0] + 1, m);
        modify(a[s[i][1]][0], 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];
        }

        assert(jump[i] > i && par[i] > i);
    }

    auto rangeQuery = [&](int l, int r) {
        assert(par[l] <= r);
        assert(r <= n);
        l = max(l, 0);
        int ans = depth[l];
        int cnt = 0;
        while (par[l] < r) {
//            assert(++cnt <= 100);
            if (par[jump[l]] < r) {
                l = jump[l];
            } else {
                l = par[l];
            }
        }
        ans -= depth[l];
        return ans + 1;
    };

    int best = rangeQuery(0, n);

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

    set<int> alive;

    for (int i = 0; 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 && par[p] > r || l != -1 && par[l] > p) {
            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 << " ";
    }

    cout << '\n';

    return 0;
}

Compilation message (stderr)

event2.cpp: In lambda function:
event2.cpp:86:13: warning: unused variable 'cnt' [-Wunused-variable]
   86 |         int cnt = 0;
      |             ^~~
event2.cpp: In function 'int main()':
event2.cpp:108:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |     for (int i = 0; alive.size() < k; ++i) {
      |                     ~~~~~~~~~~~~~^~~
event2.cpp:114:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  114 |         if (r != n && par[p] > r || l != -1 && par[l] > p) {
      |             ~~~~~~~^~~~~~~~~~~~~

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