#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mx = 2'000'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());
while(1)
{
if(M <= 0) break;
if(!nw.empty())
{
ans += nw.back();
nw.pop_back();
}
ans += 2;
M--;
}
cout << ans << '\n';
// for(int q: nw) cerr << q << ' ';
// cerr << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
8140 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
8140 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
8100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
8140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8140 KB |
Output is correct |
2 |
Correct |
13 ms |
8396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
8260 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
8420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
8524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
11376 KB |
Output is correct |
2 |
Correct |
213 ms |
15908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
155 ms |
13740 KB |
Output is correct |
2 |
Incorrect |
340 ms |
19620 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
468 ms |
25516 KB |
Output is correct |
2 |
Correct |
546 ms |
28584 KB |
Output is correct |
3 |
Correct |
612 ms |
32032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
725 ms |
31624 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
786 ms |
36692 KB |
Output is correct |
2 |
Correct |
786 ms |
36648 KB |
Output is correct |
3 |
Correct |
630 ms |
36760 KB |
Output is correct |
4 |
Correct |
750 ms |
36628 KB |
Output is correct |