#include <bits/stdc++.h>
using namespace std;
#define BEGIN 0
#define END 1
int TYPE = BEGIN;
struct interval {
int s, t, idx;
bool operator<(interval o) {
if (TYPE == BEGIN) return s < o.s;
else return t < o.t;
}
bool overlaps(interval o) {
// intersection [max(s, o.s); min(t, o.t)]
return max(s, o.s) < min(t, o.t);
}
};
struct event {
interval inter;
int type;
bool operator<(event o) {
int time = (type == BEGIN ? inter.s : inter.t);
int otime = (o.type == BEGIN ? o.inter.s : o.inter.t);
if (time == otime) {
return type == END && o.type != END;
}
return time < otime;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k; cin >> n >> k;
vector<interval> intervals(n);
for (auto& e : intervals) cin >> e.s >> e.t;
for (int i = 0; i < n; i++) intervals[i].idx = i;
// intervals.push_back({-1, -1, -1});
// intervals.push_back({(int)1e9+1, (int)1e9+1, -1});
vector<event> events(2*n);
for (int i = 0; i < n; i++) {
events[2*i] = {intervals[i], BEGIN};
events[2*i+1] = {intervals[i], END};
}
vector<bool> included(n, 1);
// for (int i = 0, K = k; i < K; i++) {
// find optimal value
vector<int> dpleft(n);
sort(events.begin(), events.end());
int curmax = 0;
for (auto [inter, type] : events) {
if (type == BEGIN) {
dpleft[inter.idx] = curmax + 1;
} else {
curmax = max(curmax, dpleft[inter.idx]);
}
}
vector<int> dpright(n);
// vector<int> next(n);
reverse(events.begin(), events.end());
curmax = 0;
int curnext = 1;
for (auto [inter, type] : events) {
if (type == END) {
dpright[inter.idx] = curmax + 1;
// next[inter.idx] = -curnext;
} else {
curmax = max(curmax, dpright[inter.idx]);
}
}
vector<int> ans;
int pointer = 0;
for (int i = 0; i < k; i++) {
while (dpright[pointer] < k-i)
if(++pointer >= n)
goto fail;
ans.push_back(pointer); // take pointer
int best = pointer;
while (intervals[pointer].s < intervals[best].t)
if(++pointer >= n)
goto fail;
}
for (int e : ans) cout << e+1 << "\n";
exit(0);
fail:
cout << "-1\n";
exit(0);
// find first possible
// for (int best = 0; best < n; best++) {
// if (!included[best]) continue;
// if (dpleft[best] + dpright[best] - 1 >= k) {
// cout << best+1 << "\n";
// included[best] = 0;
// for (int j = 0; j < n; j++) {
// if (intervals[best].overlaps(intervals[j]))
// included[j] = 0;
// }
// k--;
// goto skip;
// }
// included[best] = 0;
// }
// cout << "-1\n";
// return 0;
// skip:
// vector<event> newevents;
// for (event e : events) {
// if (included[e.inter.idx]) newevents.push_back(e);
// }
// events = newevents;
// }
return 0;
}
# | 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... |