#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i ++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) begin(X), end(X)
#define sz(X) ((int)X.size())
#define st first
#define nd second
#define vi vector<int>
#define pii pair<int, int>
#define ll long long
#define vll vector<long long>
#ifdef LOC
auto &operator<<(auto &out, pair<auto, auto> a) {
return out << "(" << a.st << ", " << a.nd << ")";
}
auto &operator<<(auto &out, auto a) {
out << "{";
for (auto b : a)
out << b << ", ";
return out << "}";
}
void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; }
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) 0
#endif
const int inf = 2e9;
const int LG = 20;
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, k;
cin >> n >> k;
vi l(n + 2), r(n + 2);
vector<vi> jmp(LG, vi(n + 2));
jmp[0][n + 1] = n + 1;
l[n + 1] = inf;
r[n + 1] = inf + 1;
l[n] = -1;
r[n] = 0;
vector<array<int, 3> > a(n + 1);
rep(i, n) {
cin >> l[i] >> r[i];
a[i] = {l[i], r[i], i};
}
a[n] = {l[n], r[n], n};
sort(all(a), greater<array<int, 3> >());
map<int, pii> dp;
dp[l[n + 1]] = {r[n + 1], n + 1};
for (auto [x, y, id] : a) {
jmp[0][id] = dp.lower_bound(y)->nd.nd;
dp[x] = min(make_pair(y, id), dp.lower_bound(y)->nd);
}
debug(jmp[0]);
fwd(i, 1, LG)
rep(j, n + 2)
jmp[i][j] = jmp[i - 1][jmp[i - 1][j]];
auto most = [&] (int v, int R) {
int ans = 0;
for (int i = LG - 1; i >= 0; i --)
if (r[jmp[i][v]] <= R) {
ans += (1 << i);
v = jmp[i][v];
debug(v);
}
return ans;
};
set<array<int, 3> > odp;
odp.insert({l[n], r[n], n});
odp.insert({l[n + 1], r[n + 1], n + 1});
int S = most(n, inf - 1);
if (S < k) {
cout << "-1\n";
return 0;
}
vi take(n, 0);
rep(i, n) {
auto nxt = odp.lower_bound({l[i], -1, -1});
if ((*nxt)[0] < r[i]) continue;
int R = (*nxt)[0];
nxt --;
if ((*nxt)[1] > l[i]) continue;
int L = (*nxt)[1];
int pid = (*nxt)[2];
int will_have = S + most(pid, l[i]) + most(i, R) - most(pid, R);
if (will_have < k - 1) continue;
take[i] = 1;
odp.insert({l[i], r[i], i});
S = will_have;
k --;
if (k == 0) break;
}
rep(i, n)
if (take[i])
cout << i + 1 << "\n";
}
Compilation message
event2.cpp: In function 'int32_t main()':
event2.cpp:29:20: warning: statement has no effect [-Wunused-value]
29 | #define debug(...) 0
| ^
event2.cpp:59:5: note: in expansion of macro 'debug'
59 | debug(jmp[0]);
| ^~~~~
event2.cpp: In lambda function:
event2.cpp:29:20: warning: statement has no effect [-Wunused-value]
29 | #define debug(...) 0
| ^
event2.cpp:69:17: note: in expansion of macro 'debug'
69 | debug(v);
| ^~~~~
event2.cpp: In function 'int32_t main()':
event2.cpp:88:13: warning: unused variable 'L' [-Wunused-variable]
88 | int L = (*nxt)[1];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
66 ms |
18332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
352 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
456 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
352 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
456 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
66 ms |
18332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
