HDU - 6119

紀念這道T了一萬年的水題。

一看問題，最多多少天，立刻想到二分，再看資料範圍，1e5，nlogn不錯呦。

接着二分答案去判定，T，然後發現小錯誤，WA，再發現小錯誤，T，優化常數，T，再優化，T.......

天啊本題多組資料這也要卡嗎，又想到是HDU的評測機評測于是懷疑這個T其實是WA。。。。。

天啊根本沒錯呀。

最後，發現直接two-point掃過去就On處理了，不需要二分，隻有前面的區間排序是nlogn複雜度，這才可以A。。。

哇，總是認定一個方法後就想不到很顯然的更簡單的方法，然後開始懷疑是不是細節有問題，沒想過是解法有問題。

诶~我還是太菜了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxl 100010

using namespace std;

int n,m,cnt,ans;
struct seg
{
	int l,r;
}a[maxl],b[maxl];
int sum[maxl];

bool cmp(const seg &x,const seg &y)
{
	if(x.l==y.l)
		return x.r<y.r;
	else
		return x.l<y.l;
}

inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}

void prework()
{
	for(int i=1;i<=n;i++)
		a[i].l=read(),a[i].r=read();
	sort(a+1,a+1+n,cmp);
	int pre=1;cnt=0;
	for(int i=2;i<=n;i++)
	if(a[i].l>=a[pre].l && a[i].l<=a[pre].r)
		a[pre].r=max(a[i].r,a[pre].r);
	else
	{
		b[++cnt]=a[pre],sum[cnt]=b[cnt].l-b[cnt-1].r-1;
		pre=i;
	}
	b[++cnt]=a[pre],sum[cnt]=b[cnt].l-b[cnt-1].r-1;
	sum[1]=0;
	for(int i=2;i<=cnt;i++)
		sum[i]=sum[i-1]+sum[i];
}

void mainwork()
{
	int r=1;ans=0;
	for(int l=1;l<=cnt;l++)
	{
		while(r<=cnt)
		{
			if(sum[r]-sum[l]>m)
				break;
			r++;
		}
		r--;
		ans=max(ans,b[r].r-b[l].l+1+m-(sum[r]-sum[l]));
	}
}

void print()
{
	printf("%d\n",ans);
}

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		prework();
		mainwork();
		print();
	}
	return 0;
}