#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());
while(1)
{
if(M <= 0) break;
if(!nw.empty())
{
ans += nw.back();
nw.pop_back();
ans += 2;
}
else ans++;
M--;
}
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 |
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 |
8440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
8524 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
8524 KB |
Output isn't 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 |
Incorrect |
6 ms |
8524 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
8524 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
8 ms |
8524 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
8644 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
8652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
10140 KB |
Output is correct |
2 |
Correct |
214 ms |
12084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
145 ms |
11200 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
488 ms |
16692 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
662 ms |
19240 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
733 ms |
22436 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |