Submission #1256939

#TimeUsernameProblemLanguageResultExecution timeMemory
1256939LucaLucaMEvent Hopping 2 (JOI21_event2)C++20
0 / 100
3096 ms4188 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cassert> #include <set> using ll = long long; #define debug(x) #x << " = " << x << '\n' const int INF = 1e9; struct Interval { int l, r; Interval() {} Interval(int _l, int _r) : l(_l), r(_r) {} bool operator < (const Interval &other) const { return l != other.l? l < other.l : r < other.r; } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); int n, k; std::cin >> n >> k; std::vector<Interval> a(n); std::vector<int> norm; for (auto &[l, r] : a) { std::cin >> l >> r; norm.push_back(l); norm.push_back(r); } std::sort(norm.begin(), norm.end()); norm.erase(std::unique(norm.begin(), norm.end()), norm.end()); for (auto &[l, r] : a) { l = std::lower_bound(norm.begin(), norm.end(), l) - norm.begin() + 1; r = std::lower_bound(norm.begin(), norm.end(), r) - norm.begin() + 1; } std::vector<Interval> b = a; std::sort(b.begin(), b.end(), [](Interval x, Interval y) { return x.r < y.r; }); std::vector<int> next(2 * n + 2, 2 * n + 2); for (const auto &[l, r] : a) { assert(1 <= l && l <= r && r <= 2 * n); next[l] = std::min(next[l], r); } for (int i = 2 * n; i >= 0; i--) { next[i] = std::min(next[i], next[i + 1]); } auto query = [&](int l, int r) { int ret = 0; int p = l; while (p <= r) { p = next[p]; ret++; } return ret; }; int maxv = 2 * n; int can = query(1, maxv); if (can < k) { std::cout << -1; return 0; } std::set<Interval> st; st.insert({0, 0}); st.insert({maxv + 1, maxv + 1}); std::vector<int> answer; for (int i = 0; i < n; i++) { auto [l, r] = a[i]; auto lt = st.lower_bound({l, 0}); --lt; auto dr = lt; ++dr; if (lt -> r <= l && r <= dr -> l) { int newCan = can - query(lt -> r, dr -> l) + query(lt -> r, l) + query(r, dr -> l) + 1; if (newCan >= k) { can = newCan; answer.push_back(i); st.insert({l, r}); } } } assert((int) answer.size() >= k); answer.resize(k); for (int x : answer) { std::cout << x + 1 << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...