Submission #976919

#	Time	Username	Problem	Language	Result	Execution time	Memory
976919		Double_Slash	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	436 ms	21196 KiB

event2

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pint;
#define all(x) x.begin(), x.end()

const int INF = 1e9;
int n, k, l[100001], r[100001], jump[100001][20], depth[100001];
set<pint> s;

int main() {
    cin >> n >> k;
    vector<int> sorted;
    for (int i = 1; i <= n; ++i) {
        cin >> l[i] >> r[i];
        r[i]--;
        sorted.emplace_back(i);
    }
    sort(all(sorted), [&] (int i, int j) { return l[i] == l[j] ? r[i] < r[j] : l[i] > l[j]; });
    int mn = INF;
    for (int i: sorted) {
        if (r[i] < mn) {
            s.emplace(l[i], i);
            auto it = s.lower_bound({r[i] + 1, 0});
            if (it != s.end()) depth[i] = depth[jump[i][0] = it->second] + 1;
            mn = r[i];
        }
    }
    for (int j = 1; j < 20; ++j) {
        for (int i = 1; i <= n; ++i) {
            jump[i][j] = jump[jump[i][j - 1]][j - 1];
        }
    }
    auto query = [&] (int ql, int qr) {
        auto it = s.lower_bound({ql, 0});
        if (it == s.end() or r[it->second] > qr) return 0;
        int i = it->second;
        int ans = depth[i];
        for (int j = 20; --j >= 0;) {
            if (jump[i][j] and r[jump[i][j]] <= qr) i = jump[i][j];
        }
        return ans - depth[i] + 1;
    };
    int cnt = query(1, INF);
    if (cnt < k) {
        cout << "-1\n";
        return 0;
    }
    set<pint> rem;
    rem.emplace(1, INF);
    for (int i = 1; i <= n and k; ++i) {
        auto it = rem.lower_bound({r[i] + 1, 0});
        if (it == rem.begin()) continue;
        auto [l0, r0] = *--it;
        if (l[i] < l0 or r[i] > r0) continue;
        int diff = query(l0, l[i] - 1) + query(r[i] + 1, r0) - query(l0, r0);
        if (cnt + diff < k - 1) continue;
        cout << i << endl;
        cnt += diff;
        k--;
        rem.erase(it);
        if (l0 <= l[i] - 1) rem.emplace(l0, l[i] - 1);
        if (r[i] + 1 <= r0) rem.emplace(r[i] + 1, r0);
    }
}

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