You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
34 lines
995 B
C++
34 lines
995 B
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 2e6 + 10;
|
|
pair<int, int> a[N];
|
|
int c[N];
|
|
int main()
|
|
{
|
|
ios::sync_with_stdio(false);
|
|
int n, k;
|
|
cin >> n >> k;
|
|
for (int i = 0, l, r; i < n; i++)
|
|
{
|
|
cin >> l >> r;
|
|
a[i << 1] = make_pair(l, -1);
|
|
a[i << 1 | 1] = make_pair(r, 1);
|
|
}
|
|
n <<= 1;
|
|
sort(a, a + n);
|
|
for (int i = 1; i <= n; i++) c[i] = -a[i - 1].second;
|
|
for (int i = 1; i <= n; i++) c[i] += c[i - 1];
|
|
for (int i = 0; i <= n; i++) c[i] -= k;
|
|
vector<pair<int, int>> ans;
|
|
for (int i = 1, st = -1; i <= n; i++)
|
|
{
|
|
if (c[i - 1] < 0 && c[i] >= 0) st = i;
|
|
if (c[i] < 0 && c[i - 1] >= 0) ans.push_back(make_pair(st - 1, i - 1));
|
|
}
|
|
cout << ans.size() << endl;
|
|
for (const auto &x : ans)
|
|
cout << a[x.first].first << ' ' << a[x.second].first << endl;
|
|
return 0;
|
|
} |