This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;
#define X first
#define Y second
#define eb emplace_back
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
template<typename T>
ostream& operator << (ostream &os, vector<T> vec) {
for (int i = 0; i < vec.size(); ++i) {
if (i) os << "\n";
os << vec[i];
}
return os;
}
const int maxn = 2E5 + 5;
#define BUILD_BUG_ON_ZERO(e) void __(){return int : !!(e);}
int n, k;
vector<int> allVal, used(maxn, 0), pre(maxn);
vector<pii> ev, perm;
int countAnswer() {
int r_bound = 0, res = 0;
for (int i = 0; i < n; ++i) {
int id = perm[i].Y;
if (pre[ev[id].Y] - pre[ev[id].X-1] or ev[id].X < r_bound) continue;
++res, r_bound = ev[id].Y;
}
return res;
}
void solve() {
cin >> n >> k, ev.resize(n), perm.resize(n);
/// discretization ///
for (auto &[l, r] : ev) cin >> l >> r, allVal.eb(l), allVal.eb(r);
sort(ALL(allVal));
allVal.resize(unique(ALL(allVal)) - begin(allVal));
for (auto &[l, r] : ev) {
l = lower_bound(ALL(allVal), l) - begin(allVal) + 1;
r = lower_bound(ALL(allVal), r) - begin(allVal) + 1;
}
for (int i = 0; i < n; ++i) perm[i] = {ev[i].Y, i};
sort(ALL(perm));
// for (auto [l, r] : ev) cout << l << " " << r << "\n";
if (countAnswer() < k) return cout << -1 << "\n", void();
vector<int> ans;
for (int i = 0; i < n; ++i) {
if (pre[ev[i].Y] - pre[ev[i].X-1]) continue;
for (int j = ev[i].X; j <= ev[i].Y; ++j) ++used[j];
partial_sum(ALL(used), begin(pre));
if (countAnswer() + ans.size() + 1 >= k) {ans.eb(i+1); continue;}
for (int j = ev[i].X; j <= ev[i].Y; ++j) --used[j];
partial_sum(ALL(used), begin(pre));
}
ans.resize(k);
cout << ans << "\n";
}
int32_t main() {
fastIO();
int t = 1; // cin >> t;
while (t--) solve();
return 0;
}
Compilation message (stderr)
event2.cpp: In function 'void solve()':
event2.cpp:69:44: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
69 | if (countAnswer() + ans.size() + 1 >= k) {ans.eb(i+1); continue;}
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
event2.cpp: In instantiation of 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>) [with T = int; std::ostream = std::basic_ostream<char>]':
event2.cpp:74:13: required from here
event2.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (int i = 0; i < vec.size(); ++i) {
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |