Submission #1439849

---

Source Code Expand

#if 0
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,f[200000],mod=1000000007,a,b,s[200000];
int main()
{
	scanf("%lld%lld%lld",&n,&a,&b);
	for(int i=1;i<=n;i++)scanf("%lld",s+i);
	if(a>b)swap(a,b);
	for(int i=2;i<n;i++)
		if(s[i+1]-s[i-1]<a){puts("0");return 0;}
	f[0]=1;s[0]=-b;
	long long sum=0,r=0;
	for(int i=1;i<=n;i++)
	{
		for(;r<i&&s[i]-s[r]>=b;r++)sum=(sum+f[r])%mod;
		f[i]=sum;
		if(s[i]-s[i-1]<a)sum=0,r=i-1;
	}
	for(int i=r;i<=n;i++)sum=(sum+f[i])%mod;
	printf("%lld\n",sum);
	return 0;
}
#else
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,a,b,s[200000],f[200000],g[200000],mod=1000000007;
int main()
{
	scanf("%lld%lld%lld",&n,&a,&b);
	if(a>b)swap(a,b);
	for(int i=1;i<=n;i++)scanf("%lld",s+i);
	s[0]=-b;
	f[0]=g[0]=1;
	for(int i=2;i<n;i++)
		if(s[i+1]-s[i-1]<a){puts("0");return 0;}
	long long sf=0,sg=0,pf=0,pg=0;
	for(int i=2;i<=n;i++)
	{
		for(;pf<i&&s[i]-s[pf]>=a;pf++)sf=(sf+f[pf])%mod;
		for(;pg<i&&s[i]-s[pg]>=b;pg++)sg=(sg+g[pg])%mod;
		if(s[i]-s[i-1]<b)sf=0,pf=i-1;
		if(s[i]-s[i-1]<a)sg=0,pg=i-1;
		f[i-1]=sg;g[i-1]=sf;
		//printf("sf=%lld,sg=%lld,pf=%lld,pg=%lld\n",sf,sg,pf,pg);
	}
	for(int i=pf;i<n;i++)sf+=f[i];
	for(int i=pg;i<n;i++)sg+=g[i];
	printf("%lld\n",(sf+sg)%mod);
	//printf("pf=%lld,pg=%lld\n",pf,pg);
	//for(int i=0;i<=n;i++)printf("(f,g)[%d]=%lld,%lld\n",i,f[i],g[i]);
	return 0;
}
#endif

Submission Info

Judge Result