#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<pair<int, int>> a(n);
vector<int> b(2 * n);
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
b[2 * i] = a[i].first;
b[2 * i + 1] = a[i].second;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for (int i = 0; i < n; i++) {
a[i].first = (int) (lower_bound(b.begin(), b.end(), a[i].first) - b.begin());
a[i].second = (int) (lower_bound(b.begin(), b.end(), a[i].second) - b.begin());
}
vector<int> c(2 * n);
for (int i = 0; i < n; i++) {
c[a[i].first] = a[i].second;
c[a[i].second] = a[i].first;
}
vector<int> was(2 * n);
vector<int> d;
int ans = 0;
for (int z = 0; z < 2 * n; z++) {
if (was[z]) {
continue;
}
int now = z;
int sz = 0;
do {
sz++;
was[now] = 1;
now = c[now] + 1;
} while (now < 2 * n && now != z);
if (z != 0) {
d.emplace_back(sz);
} else {
ans = sz;
}
}
sort(d.rbegin(), d.rend());
int t = 0;
for (int i = 0; i < m; i++) {
if (i < (int) d.size()) {
ans += d[i] + 2;
} else if (t) {
ans += 3;
t ^= 1;
} else {
ans++;
t ^= 1;
}
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
6 ms |
708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
460 KB |
Output is correct |
2 |
Correct |
7 ms |
844 KB |
Output is correct |
3 |
Correct |
18 ms |
1536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
4836 KB |
Output is correct |
2 |
Correct |
178 ms |
10512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
137 ms |
7744 KB |
Output is correct |
2 |
Correct |
266 ms |
15124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
396 ms |
22200 KB |
Output is correct |
2 |
Correct |
441 ms |
28616 KB |
Output is correct |
3 |
Correct |
464 ms |
41920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
598 ms |
32224 KB |
Output is correct |
2 |
Correct |
646 ms |
45432 KB |
Output is correct |
3 |
Correct |
540 ms |
31516 KB |
Output is correct |
4 |
Correct |
550 ms |
31840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
635 ms |
50332 KB |
Output is correct |
2 |
Correct |
619 ms |
50364 KB |
Output is correct |
3 |
Correct |
450 ms |
50340 KB |
Output is correct |
4 |
Correct |
569 ms |
50332 KB |
Output is correct |