1 条题解
-
0

#include <cstdio> #include <iostream> using namespace std; const int M = 100005; const int MOD = 1e9+7; #define int long long int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,A,B,ans,a[M],f[M],s[M]; signed main() { n=read();A=read();B=read(); if(A<B) swap(A,B); for(int i=1;i<=n;i++) a[i]=read(); for(int i=3;i<=n;i++) if(a[i]-a[i-2]<B) { puts("0"); return 0; } f[0]=s[0]=1; for(int i=1,p=0,q=0;i<=n;i++) { while(q<i && a[i]-a[q+1]>=A) q++; if(p<=q) f[i]=(s[q]-(p?s[p-1]:0))%MOD; s[i]=(s[i-1]+f[i])%MOD; if(i>1 && a[i]-a[i-1]<B) p=i-1; } for(int i=n;i>=0;i--) { ans=(ans+f[i])%MOD; if(i<n && a[i+1]-a[i]<B) break; } printf("%lld\n",(ans+MOD)%MOD); }
- 1
信息
- ID
- 8755
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 5
- 已通过
- 1
- 上传者