3629. Channel On Live（扫描线）

3629. Channel On Live（扫描线）

EOJ has recently opened a new live channel, so that coders can broadcast their coding online and chat with the audience at the same time. It has become children’s favorite entertainment at night, well, other than the monthly contest.

It may sound hard to believe, but the EOJ team has recently encountered some trouble in terms of the live channel statistics. Basically they want to know two things:

The maximum number of children watching the live channel simultaneously;The average number of children online, during the show, which starts atthe beginning of second 1and ends atthe end of secondm.

Input

The first line contains two space-separated integers n and m (1≤n≤250 000, 1≤m≤109), denoting the number of children log-in record, the length of the show.

The next n line each contains two space-separated integers si and ti (1≤si≤ti≤m), meaning that a child starts to watch the channel at the start of second si, and leave the channel at the end of second ti. Notice that the same pair of (s,t) might appear multiple times, they are believed to be different records.

You can safely assume that these records all belong to different children.

Output

In the first line, output the maximum number. You can write it as an integer, or a floating number, as you like.

In the second line, output the average number as a floating number.

The absolute or relative error should be not greater than 10−12.

Examples

input

2 101 55 10

output

21.1

input

4 101 34 48 85 7

output

18E-1

input

5 105 64 73 82 91 10

output

5.0000000000000003

求区间覆盖最大值，扫描线的模板。

平均值，就是所有区间孩子的总数，除区间总长度吧

代码：

#include #define ll long longusing namespace std;const int maxn =3e5+100;struct node{ double id,w;}G[maxn*3];bool cmp(node a,node b){ if(a.idb.w)return 1; return 0; } return 0;}int main(){ int n,m; scanf("%d%d",&n,&m); int ans=0; double u,v; double sum_1=0; for(int i=1;i<=n;i++) { scanf("%lf%lf",&u,&v); sum_1+=v-u+1; G[ans].id=u; G[ans++].w=1; G[ans].id=v; G[ans++].w=-1; } sort(G,G+ans,cmp); ll sum=0; ll max_1=0; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。