#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mx = 2'100'000;
int* nxt;
int main()
{
int N, M;
cin >> N >> M;
vector<int> ep(1+mx+1, 0);
for(int i = 1; i <= N; i++)
{
int W, E;
cin >> W >> E;
ep[W] = +i;
ep[E] = -i;
}
nxt = new int[mx + 100'000];
nxt = nxt + mx/2 + 50'000;
int lst = 0;
for(int p = mx; p >= 0; p--)
{
if(ep[p] == 0) continue;
// cerr << "x = " << p << ' ' << ep[p] << '\n';
nxt[ep[p]] = lst;
lst = ep[p];
}
nxt[0] = 0;
// for(int i = 1; i <= N; i++) cerr << nxt[+i] << ' ' << nxt[-i] << '\n';
vector<int> nw;
bool* visit = new bool[mx + 100'000] + (mx/2 + 50'000);
for(int i = 1; i <= N; i++) visit[i] = visit[-i] = 0;
for(int p = 1; p <= mx; p++)
{
if(ep[p] == 0) continue;
if(visit[-ep[p]]) continue;
nw.push_back(0);
for(int u = -ep[p]; u != 0 && !visit[u]; u = -nxt[u])
{
visit[u] = 1;
nw[int(nw.size()-1)]++;
}
}
reverse(nw.begin(), nw.end());
int mn = nw.back();
nw.pop_back();
// cerr << "mn = " << mn << '\n';
//
// for(int f: nw) cerr << f << ' ';
// cerr << '\n';
int ans = mn;
sort(nw.begin(), nw.end());
int l = 0;
while(1)
{
if(M <= 0) break;
if(!nw.empty())
{
ans += nw.back();
nw.pop_back();
ans += 2;
}
else
{
ans += 2;
l = !l;
}
M--;
}
if(l % 2 == 1)
ans--;
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
8524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
8524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
8524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
8524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
8524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8524 KB |
Output is correct |
2 |
Correct |
16 ms |
8652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8524 KB |
Output is correct |
2 |
Correct |
14 ms |
8780 KB |
Output is correct |
3 |
Correct |
21 ms |
9116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
8648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
8712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
10036 KB |
Output is correct |
2 |
Correct |
206 ms |
12092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
147 ms |
11184 KB |
Output is correct |
2 |
Correct |
307 ms |
13484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
497 ms |
16676 KB |
Output is correct |
2 |
Correct |
563 ms |
18196 KB |
Output is correct |
3 |
Correct |
537 ms |
20776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
635 ms |
19308 KB |
Output is correct |
2 |
Correct |
687 ms |
33840 KB |
Output is correct |
3 |
Correct |
717 ms |
32704 KB |
Output is correct |
4 |
Correct |
715 ms |
32828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
706 ms |
22456 KB |
Output is correct |
2 |
Correct |
699 ms |
22452 KB |
Output is correct |
3 |
Correct |
589 ms |
22448 KB |
Output is correct |
4 |
Correct |
651 ms |
22448 KB |
Output is correct |