#include <iostream>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
#define ll long long
using namespace std;
vector <ll> adj[200001], V;
ll n, k, x, y, s, z, X[200001], bl[200001][18], D[200001], mxdepth[200001];
map <ll, array<ll, 3>> mp;
priority_queue <array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>> > pq;
array <ll, 3> R[200001];
ll binlift(ll u, ll r) {
ll du = D[u];
for (int i=17; i>=0; --i) {
if (r <= R[bl[u][i]][0] && bl[u][i] != n) {
u = bl[u][i];
}
}
return du-D[u];
}
void dfs(ll u) {
s = max(s, mxdepth[u]);
for (auto v : adj[u]) {
mxdepth[v] = mxdepth[u] + 1;
dfs(v);
}
}
int main() {
cin >> n >> k;
for (int i=0; i<n; ++i) {
cin >> R[i][0] >> R[i][1];
R[i][2] = i;
}
sort(R, R+n);
for (int i=0; i<n; ++i) X[R[i][2]] = i;
x = -1e18, y = n;
for (int i=0; i<n; ++i) {
while (!pq.empty()) {
auto [r, l, id] = pq.top();
if (r <= R[i][0]) {
pq.pop();
adj[i].push_back(id);
if (l > x) {
x = l;
y = id;
}
}
else break;
}
//cout << y << " " << i << " " << R[i][0] << " " << R[i][1] << '\n';
bl[i][0] = y;
D[i] = D[y]+1;
pq.push({R[i][1], R[i][0], i});
}
bl[n][0] = n;
for (int j=1; j<18; ++j) {
for (int i=0; i<=n; ++i) {
bl[i][j] = bl[bl[i][j-1]][j-1];
}
}
while (!pq.empty()) {
auto [r, l, id] = pq.top();
pq.pop();
adj[n].push_back(id);
}
dfs(n);
if (s < k) {
cout << "-1\n";
return 0;
}
mp[0] = {0, s, n};
for (int j=0; j<n; ++j) {
int i = X[j];
auto it = mp.lower_bound(R[i][1]);
//cout << it->second[2] << " " << R[i][1] << '\n';
if (it != mp.end()) z = binlift(it->second[2], R[i][1]);
else z = mxdepth[i]-1;
it = prev(it);
if (it->second[0] > R[i][0]) continue;
x = it->second[1];
y = binlift(i, it->second[0]);
if (s-x+y+z+1 >= k) {
s = s-x+y+z+1;
mp[it->first] = {it->second[0], y, it->second[2]};
mp[R[i][0]] = {R[i][1], z, i};
V.push_back(j);
}
}
for (int i=0; i<k; ++i) {
cout << V[i]+1 << '\n';
}
}
Compilation message
event2.cpp: In function 'int main()':
event2.cpp:45:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | auto [r, l, id] = pq.top();
| ^
event2.cpp:68:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | auto [r, l, id] = pq.top();
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11612 KB |
Output is correct |
2 |
Correct |
4 ms |
11612 KB |
Output is correct |
3 |
Correct |
5 ms |
11612 KB |
Output is correct |
4 |
Incorrect |
82 ms |
37512 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
11608 KB |
Output is correct |
2 |
Correct |
2 ms |
11608 KB |
Output is correct |
3 |
Correct |
2 ms |
11612 KB |
Output is correct |
4 |
Correct |
2 ms |
11612 KB |
Output is correct |
5 |
Correct |
3 ms |
11612 KB |
Output is correct |
6 |
Correct |
2 ms |
11612 KB |
Output is correct |
7 |
Incorrect |
2 ms |
11612 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
11608 KB |
Output is correct |
2 |
Correct |
2 ms |
11608 KB |
Output is correct |
3 |
Correct |
2 ms |
11612 KB |
Output is correct |
4 |
Correct |
2 ms |
11612 KB |
Output is correct |
5 |
Correct |
3 ms |
11612 KB |
Output is correct |
6 |
Correct |
2 ms |
11612 KB |
Output is correct |
7 |
Incorrect |
2 ms |
11612 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11612 KB |
Output is correct |
2 |
Correct |
4 ms |
11612 KB |
Output is correct |
3 |
Correct |
5 ms |
11612 KB |
Output is correct |
4 |
Incorrect |
82 ms |
37512 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |