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 points and no others.
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 ( - 109 ≤ 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 — the smallest number of segments.
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.
Example
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
一开始思路就错了，先用了离散化，然后再前缀和计算覆盖数，但是这种写法，没有办法记录到点，只能记录线段。第17个case就错了。
这题我觉得算是区间版的离散和，动态维护覆盖数。本质是一样的。
#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#define maxx 10050
#define mod 9901
using namespace std;
struct node
{
int val;
int o;
}p[2000005];
bool cmp(node x1, node x2)
{
if(x1.val!=x2.val)
return x1.val<x2.val;
return x1.o>x2.o;
}
int l[1000005];
int r[1000005];
int cnt=0;
int main()
{
int n,k;
cin>>n>>k;
int x,y;
for(int i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
p[cnt].val=x;
p[cnt++].o=1;
p[cnt].val=y;
p[cnt++].o=0;
}
sort(p,p+cnt,cmp);
int countt=0;
int t=0;
int i=0;
bool sign=false;
while(i<cnt)
{
if(p[i].o)
{
countt++;
if(!sign)
if(countt>=k)
l[t]=p[i].val,sign=true;
}
else
{
countt--;
if(sign)
if(countt<k)
r[t++]=p[i].val,sign=false;
}
i++;
}
cout<<t<<endl;
for(int i=0;i<t;i++)
cout<<l[i]<<" "<<r[i]<<endl;
return 0;
}