#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;
M--;
}
cout << ans << '\n';
// for(int q: nw) cerr << q << ' ';
// cerr << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
8488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
8576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
8524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
8532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
8524 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
8524 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
8524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
8532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8524 KB |
Output is correct |
2 |
Correct |
12 ms |
8796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
8 ms |
8576 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
8772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
93 ms |
10180 KB |
Output is correct |
2 |
Correct |
212 ms |
12208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
142 ms |
11320 KB |
Output is correct |
2 |
Incorrect |
332 ms |
13668 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
472 ms |
16808 KB |
Output is correct |
2 |
Correct |
527 ms |
18088 KB |
Output is correct |
3 |
Correct |
522 ms |
20904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
619 ms |
19380 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
719 ms |
22632 KB |
Output is correct |
2 |
Correct |
702 ms |
22564 KB |
Output is correct |
3 |
Correct |
586 ms |
22580 KB |
Output is correct |
4 |
Correct |
646 ms |
22640 KB |
Output is correct |