oj.uz

Submission #871914

# Submission time Handle Problem Language Result Execution time Memory
871914 2023-11-11T21:00:14 Z tvladm2009 Event Hopping 2 (JOI21_event2) C++17
0 / 100
 1 ms 348 KB 
#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);
        }
        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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -