D. The Union of k-Segments
time limit per test
memory limit per test
input
output
You are given n segments on the coordinate axis Ox and the number k. The point is satisfied if it belongs to at least k segments. Find the smallest (by the number of segments) set of segments on the coordinate axis Ox which contains all satisfied
Input
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 106) — the number of segments and the value of k.
The next n lines contain two integers li, ri (9 ≤ li ≤ ri ≤ 109) each — the endpoints of the i-th segment. The segments can degenerate and intersect each other. The segments are given in arbitrary order.
Output
First line contains integer m
Next m lines contain two integers aj, bj (aj ≤ bj) — the ends of j-th segment in the answer. The segments should be listed in the order from left to right.
Examples
input
3 2
0 5
-3 2
3 8
output
2
0 2
3 5
input
3 2
0 5
-3 3
3 8
output
1
0 5
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
typedef long long ll;
struct Node{
Node(){
}
Node(int a, int b){
l = a;
r = b;
}
int l, r;
}node[maxn];
vector<Node> v;
int n, k, d[maxn<<1], p[maxn<<1];
int main(){
// freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++){
scanf("%d%d", &node[i].l, &node[i].r);
d[2*i] = node[i].l;
d[2*i+1] = node[i].r;
}
sort(d, d+2*n);
int cnt = 2 * n;
for(int i = 0; i < n; i++){
int k1 = lower_bound(d, d+cnt, node[i].l) - d;
p[k1+1]++;
int k2 = upper_bound(d, d+cnt, node[i].r) - d;
p[k2]--;
}
for(int i = 1; i <= cnt; i++)
p[i] += p[i-1];
int l = -1, r = -1;
for(int i = 0; i <= cnt; i++){
if(l == -1 && p[i] >= k)
l = i;
if(l != -1 && p[i] < k){
r = i;
v.push_back(Node(d[l-1], d[r-1]));
l = -1;
}
}
printf("%d\n", v.size());
for(int i = 0; i < v.size(); i++)
printf("%d %d\n", v[i].l, v[i].r);
return 0;
}