记录编号	485624	评测结果	AAWWAWWWWW
题目名称	[NOIP 2017PJ]跳房子	最终得分	30
用户昵称	+1s	是否通过	未通过
代码语言	C++	运行时间	2.948 s
提交时间	2018-02-01 16:40:27	内存使用	12.28 MiB

#include<cstdio>
#include<cstring>
#define OO 2000000000
#define PUSH q[rear++]=
#define POPHEAD front++;
#define POPTAIL rear--;
#define DETMAX (d+m)
#define DETMIN ((d-m)>0?(d-m):1)
long long tp,re[500050];
int n,d,k,front,rear;
struct{long long x,s;}data[500050];
int q[500050];
long long check(long long m)//f[i]=max(f[j])+s[i](i+d-g<=x[j]<=i+d+g)
{
	memset(re,0,sizeof(re));
	front=1,rear=0;
	int j=0;
	for(int i=1;i<=n;i++)
	{
		while(j==0||(data[i].x-DETMAX<=data[j].x&&data[j].x<=data[i].x-DETMIN))
		{
			while(rear>front&&re[j]>re[q[rear-1]])POPTAIL
			PUSH j++;
		}
		while(rear>front&&!(data[i].x-DETMAX<=data[q[front]].x&&data[q[front]].x<=data[i].x-DETMIN))POPHEAD
		if(rear>front)re[i]=re[q[front]]+data[i].s;
		else if(DETMIN+data[j-1].x<=data[i].x&&data[i].x<=DETMAX+data[j-1].x)re[i]=data[i].s;
	}
	int xm=-1;
	for(int i=1;i<=n;i++)xm=xm>re[i]?xm:re[i];
	return xm;
}
int main()
{
	freopen("jumpplane.in","r",stdin);
	freopen("jumpplane.out","w",stdout);
	scanf("%d %d %d",&n,&d,&k);
	memset(data,0,sizeof(data));
	for(int i=1;i<=n;i++)
	{
		scanf("%lld %lld",&((data+i)->x),&((data+i)->s));
		if((data+i)->s>0)tp+=(data+i)->s;
	}
	if(tp<k)
	{
		printf("%d",-1);
		return 0;
	}	
	long long l=0,r=data[n].x;
	while(l<r)
	{
		long long m=(l+r)/2;
		memset(q,0,sizeof(q));
		if(check(m)>=k)r=m;
		else l=m+1;
	}
	printf("%lld",l);
	return 0;
}