Submission #3428216

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
LL read() {
	LL q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10LL+(LL)(ch-'0'),ch=getchar();
	return q;
}
const int mod=1e9+7,N=100005;
const LL inf=2e18;
int n,Log[N],bin[17],f[N][2],sum[N][2];
LL X[2],a[N],mi[17][N];
int qm(int x) {return x>=mod?x-mod:x;}
void prework() {
	bin[0]=1;for(RI i=1;i<=16;++i) bin[i]=bin[i-1]<<1;
	Log[0]=-1;for(RI i=1;i<=n;++i) Log[i]=Log[i>>1]+1;
	for(RI j=1;j<=16;++j)
		for(RI i=1;i+bin[j]-1<=n;++i)
			mi[j][i]=min(mi[j-1][i],mi[j-1][i+bin[j-1]]);
}
LL getmi(int l,int r) {
	if(l>r) return inf;
	int t=Log[r-l+1];
	return min(mi[t][l],mi[t][r-bin[t]+1]);
}
int findl(int x,int o) {
	int l=0,r=x-1,mid,re=0;
	while(l<=r) {
		mid=(l+r)>>1;
		if(getmi(mid+2,x)>=X[o]) re=mid,r=mid-1;
		else l=mid+1;
	}
	return re;
}
int main()
{
	n=read(),X[0]=read(),X[1]=read();
	for(RI i=1;i<=n;++i) a[i]=read(),mi[0][i]=a[i]-a[i-1];
	prework();
	f[0][0]=f[0][1]=sum[0][0]=sum[0][1]=1;
	a[n+1]=inf;
	for(RI i=1;i<=n;++i) {
		int l=findl(i,0);
		int r=upper_bound(a+1,a+i,a[i+1]-X[1])-a-1;
		if(l<=r) f[i][0]=qm(sum[r][1]-sum[l-1][1]+mod);
		l=findl(i,1);
		r=upper_bound(a+1,a+i,a[i+1]-X[0])-a-1;
		if(l<=r) f[i][1]=qm(sum[r][0]-sum[l-1][0]+mod);
		sum[i][0]=qm(sum[i-1][0]+f[i][0]);
		sum[i][1]=qm(sum[i-1][1]+f[i][1]);
	}
	printf("%d\n",qm(f[n][0]+f[n][1]));
	return 0;
}

Submission Info

Judge Result