Submission #871915

#	Time	Username	Problem	Language	Result	Execution time	Memory
871915		tvladm2009	Event Hopping 2 (JOI21_event2)	C++17	7 / 100	25 ms	4576 KiB

event2

#include <bits/stdc++.h>
 
using i64 = long long;
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k;
    std::cin >> n >> k;
    std::vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        std::cin >> l[i] >> r[i];
    }
    std::vector<int> dp(n, 0), suff(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        int lft = i + 1, rgh = n - 1, pos = n;
        while (lft <= rgh) {
            int m = (lft + rgh) / 2;
            if (l[m] >= r[i]) {
                rgh = m - 1;
                pos = m;
            } else {
                lft = m + 1;
            }
        }
        dp[i] = suff[pos] + 1;
        suff[i] = std::max(suff[i + 1], dp[i]);
    }
    std::vector<int> sol;
    int last = 0;
    for (int i = 0; i < n; i++) {
        if (l[i] >= last && dp[i] >= k) {
            last = r[i];
            k--;
            sol.push_back(i + 1);
        }
        if (k == 0) {
            break;
        }
    }
    if (k > 0) {
        std::cout << "-1\n";
        return 0;
    }
    for (auto it : sol) {
        std::cout << it << "\n";
    }
    return 0;
}

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