Submission #1150678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150678		Sharky	Event Hopping 2 (JOI21_event2)	C++20	0 / 100	137 ms	54356 KiB

event2

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define fi first
#define se second

#define L(i, j, k) for (int i = (j); i <= (k); i++)
#define R(i, j, k) for (int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()

const int LG = 18;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> l(n+1), r(n+1);
    set<array<int, 3>> st;
    vector<int> disc;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        disc.push_back(l[i]);
        disc.push_back(r[i]);
    }
    sort(disc.begin(), disc.end());
    disc.erase(unique(disc.begin(), disc.end()), disc.end());
    int m = 0;
    for (int i = 1; i <= n; i++) {
        l[i] = lower_bound(disc.begin(), disc.end(), l[i]) - disc.begin() + 1;
        r[i] = lower_bound(disc.begin(), disc.end(), r[i]) - disc.begin() + 1;
        m = max(m, r[i]);
        // debug(l[i], r[i]);
    }
    vector<int> pos[m+1];
    vector<vector<int>> lift(m+2, vector<int> (LG, 0));
    for (int i = 1; i <= n; i++) pos[l[i]].push_back(r[i]);
    int mini = m+1;
    lift[m+1][0] = m+1;
    for (int i = m; i >= 0; i--) {
        for (auto& rb : pos[i]) mini = min(mini, rb);
        lift[i][0] = mini;
    }
    for (int i = 1; i < LG; i++) {
        for (int j = 0; j <= m+1; j++) lift[j][i] = lift[lift[j][i-1]][i-1];
    }
    // cout << lift[0][0] << ' ' << lift[0][1] << '\n';
    auto count = [&] (int lb, int rb) {
        if (lb > rb) return 0LL;
        int res = 0, sp = lb-1;
        for (int i = LG - 1; i >= 0; i--) {
            if (lift[sp][i] <= rb) {
                // debug(sp, i, lift[sp][i], lb, rb, res);
                sp = lift[sp][i], res += (1 << i);
            }
        }
        return res;
    };
    int sum = count(1, m);
    st.insert({1, m, sum});
    // debug(sum);
    if (sum < k) {
        cout << "-1\n";
        return;
    }
    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        auto it = st.lower_bound({l[i]+1, 0, 0});
        if (it == st.begin()) continue;
        --it;
        auto [ll, rr, val] = *it;
        // debug(ll, rr, val);
        if (ll <= l[i] && r[i] <= rr) {
            int lp = count(ll, l[i]);
            int rp = count(r[i], rr);
            if (sum - val + lp + rp + 1 >= k) {
                st.erase({ll, rr, val});
                if (ll <= l[i]) st.insert({ll, l[i], lp});
                if (r[i] <= rr) st.insert({r[i], rr, rp});
                sum = sum - val + lp + rp + 1;
                ans.push_back(i);
                if (ans.size() >= k) break;
            }
        }
    }
    for (int e : ans) cout << e << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) solve();
}

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