#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; } template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; } const int MAXN = 2e5 + 5; int n, k; pair<int, int> e[MAXN]; namespace sub1 { int bit[MAXN], dp[MAXN]; vector<int> comp; void add(int i, int v) { for (; i > 0; i -= i & -i) ckmax(bit[i], v); } int get(int i) { int ans = 0; for (; i <= (int)comp.size(); i += i & -i) ckmax(ans, bit[i]); return ans; } void solve() { for (int i = 1; i <= n; i++) { comp.emplace_back(e[i].fi); comp.emplace_back(e[i].se); } sort(comp.begin(), comp.end()); comp.resize(unique(comp.begin(), comp.end()) - comp.begin()); for (int i = 1; i <= n; i++) { e[i].fi = lower_bound(comp.begin(), comp.end(), e[i].fi) - comp.begin() + 1; e[i].se = lower_bound(comp.begin(), comp.end(), e[i].se) - comp.begin() + 1; } for (int i = n; i >= 1; i--) { dp[i] = get(e[i].se) + 1; add(e[i].fi, dp[i]); } vector<int> ans; for (int i = 1; i <= n; i++) { if (get(e[i].se) >= k - (int)ans.size() - 1 && (ans.empty() || e[ans.back()].se <= e[i].fi)) ans.emplace_back(i); if ((int)ans.size() == k) break; } if (ans.size() < k) cout << -1 << '\n'; else for (int x : ans) cout << x << '\n'; } } namespace sub4 { int m; int bit[MAXN]; pair<int, int> b[MAXN]; vector<int> comp; int minPos[MAXN]; const int LG = 18; int up[MAXN][LG + 1]; void add(int i, int v) { for (; i > 0; i -= i & -i) ckmin(bit[i], v); } int get(int i) { int ans = m + 1; for (; i <= m; i += i & -i) ckmin(ans, bit[i]); return ans; } int countSegment(int l, int r) { int ans = 0; for (int i = LG; i >= 0; i--) { if (up[l][i] <= r) { ans |= (1 << i); l = up[l][i]; } } return ans; } void solve() { for (int i = 1; i <= n; i++) { comp.emplace_back(e[i].fi); comp.emplace_back(e[i].se); } sort(comp.begin(), comp.end()); comp.resize(unique(comp.begin(), comp.end()) - comp.begin()); m = comp.size(); for (int i = 1; i <= n; i++) { e[i].fi = lower_bound(comp.begin(), comp.end(), e[i].fi) - comp.begin() + 1; e[i].se = lower_bound(comp.begin(), comp.end(), e[i].se) - comp.begin() + 1; b[i] = e[i]; debug(b[i]); } sort(b + 1, b + n + 1); for (int i = 1; i <= m; i++) bit[i] = minPos[i] = m + 1; for (int i = 1; i <= n; i++) { ckmin(minPos[b[i].fi], b[i].se); } up[m + 1][0] = m + 1; for (int i = m; i >= 1; i--) { add(i, minPos[i]); up[i][0] = get(i); } for (int j = 1; j <= LG; j++) { for (int i = 1; i <= m + 1; i++) { up[i][j] = up[up[i][j - 1]][j - 1]; } } set<pair<int, int>> seg; if (countSegment(1, m) < k) { cout << -1 << '\n'; return; } seg.emplace(0, 1); seg.emplace(m, m); int cntChose = 0, curValid = countSegment(1, m); for (int i = 1; i <= n; i++) { if (cntChose >= k) break; auto it = seg.lower_bound({e[i].fi, 0}); if (it->fi < e[i].se) continue; if (prev(it)->se > e[i].fi) continue; int tmp = curValid; tmp -= countSegment(prev(it)->se, it->fi); tmp += countSegment(prev(it)->se, e[i].fi) + countSegment(e[i].se, it->fi); if (tmp >= k - cntChose - 1) { cntChose++; curValid = tmp; cout << i << '\n'; seg.insert(e[i]); } } } } int main() { #define NAME "test" if (fopen(NAME".inp", "r")) { freopen(NAME".inp", "r", stdin); freopen(NAME".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k; bool checkSub1 = 1; for (int i = 1; i <= n; i++) { cin >> e[i].fi >> e[i].se; // debug(e[i].fi, e[i - 1].fi, e[i].fi < e[i - 1].fi); if (i > 1 && e[i].fi < e[i - 1].fi) checkSub1 = 0; } if (checkSub1) sub1::solve(); else sub4::solve(); return 0; }

event2.cpp: In function 'int main()':
event2.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
event2.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~