Submission #2587230
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define llu unsigned long long
#define ld double
#define llu unsigned long long
#define rep(i,x,y) for(int i=int(x);i<int(y);++i)
#define For(i,x,y) for(int i=int(x);i<=int(y);++i)
#define FOr(i,x,y) for(int i=int(x);i>=int(y);--i)
#define pi acos(-1)
#define mk make_pair
#define pa pair<ll,ll>
#define lf else if
#define IL inline
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)<(y)?(x):(y))
#define sqr(x) ((x)*(x))
#define Mul(x,y) ((x)=1LL*(x)*(y)%mod)
#define Add(x,y) ((x)=((x)+(y))%mod)
#define Max(x,y) ((x)=((x)<(y)?(y):(x)))
#define Min(x,y) ((x)=((x)>(y)?(y):(x)))
#define E(x) return writeln(x),0
#define LL (long long)
#define p(x) printf("~%lld~\n",LL(x))
#define pp(x,y) printf("~~%lld %lld~~\n",LL(x),LL(y))
#define ppp(x,y,z) printf("~~~%lld %lld %lld~~~\n",LL(x),LL(y),LL(z))
#define pppp(a,b,c,d) printf("~~~%lld %lld %lld %lld\n",LL(a),LL(b),LL(c),LL(d))
#define f_in(x) freopen(x".in","r",stdin)
#define f_out(x) freopen(x".out","w",stdout)
#define open(x) f_in(x),f_out(x)
#define fi first
#define se second
#define GuYue puts("\nGuYueNa________________________________________________________________________________")
typedef complex<double> E;
namespace cqz{
#ifdef LOCAL
struct _{_(){freopen("cf.in","r",stdin);}}_;
#endif
#define NEG 1
static const int GYN=2333333;
char SZB[GYN],*S=SZB,*T=SZB;
inline char gc(){ if (S==T){ T=(S=SZB)+fread(SZB,1,GYN,stdin); if (S==T) return '\n'; } return *S++; }
#if NEG
inline ll read(){ ll x=0,g=1; char ch=gc(); for (;!isdigit(ch);ch=gc()) if (ch=='-') g=-1; for (;isdigit(ch);ch=gc()) x=x*10-48+ch; return x*g; }
inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
#else
inline ll read(){ ll x=0; char ch=gc(); for (;!isdigit(ch);ch=gc()); for (;isdigit(ch);ch=gc()) x=x*10-48+ch; return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
#endif
inline char readchar(){ char ch=gc(); for(;isspace(ch);ch=gc()); return ch; }
inline ll readstr(char *s){ char ch=gc(); int cur=0; for(;isspace(ch);ch=gc()); for(;!isspace(ch);ch=gc()) s[cur++]=ch; s[cur]='\0'; return cur; }
void Print(long long *a,int s,int t){For(i,s,t)printf("%lld ",a[i]);}
void Print(int *a,int s,int t){For(i,s,t)printf("%d ",a[i]);}
void Print(char *a,int s,int t){For(i,s,t)putchar(a[i]);}
void writeln(ll x){write(x);puts("");}
}using namespace cqz;
const ll mod=1e9+7,N=100010;
ll sum[N],f[N],a[N],n,A,B,last,pos;
ll Qsum(ll x,ll y){if (x>y)return 0;return (sum[y]-(x?sum[x-1]:0ll))%mod;}
int main(){
n=read(),A=read(),B=read();if (A>B)swap(A,B);
For(i,1,n)a[i]=read();a[++n]=2e18;
f[1]=f[0]=sum[0]=1; sum[1]=2;
For(i,3,n)if (a[i]-a[i-2]<A)return puts("0"),0;
last=0;pos=0;
For(i,2,n){
for(;a[i]-a[pos+1]>=B;++pos);
f[i]=Qsum(last,pos);
sum[i]=(sum[i-1]+f[i])%mod;
if (a[i]-a[i-1]<A)last=i-1;
}
writeln((f[n]+mod)%mod);
}
/*
f[i] i是b的答案...
*/
Submission Info
Submission Time |
|
Task |
C - Division into Two |
User |
SHENZHEBEI |
Language |
C++14 (GCC 5.4.1) |
Score |
1100 |
Code Size |
3209 Byte |
Status |
AC |
Exec Time |
6 ms |
Memory |
4480 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1100 / 1100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt, s3.txt, s4.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, s1.txt, s2.txt, s3.txt, s4.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
6 ms |
4352 KB |
02.txt |
AC |
6 ms |
4352 KB |
03.txt |
AC |
6 ms |
4352 KB |
04.txt |
AC |
6 ms |
4352 KB |
05.txt |
AC |
5 ms |
4352 KB |
06.txt |
AC |
6 ms |
4352 KB |
07.txt |
AC |
6 ms |
4352 KB |
08.txt |
AC |
6 ms |
4352 KB |
09.txt |
AC |
6 ms |
4352 KB |
10.txt |
AC |
6 ms |
4352 KB |
11.txt |
AC |
6 ms |
4352 KB |
12.txt |
AC |
6 ms |
4352 KB |
13.txt |
AC |
6 ms |
4352 KB |
14.txt |
AC |
6 ms |
4352 KB |
15.txt |
AC |
6 ms |
4352 KB |
16.txt |
AC |
4 ms |
4352 KB |
17.txt |
AC |
4 ms |
4352 KB |
18.txt |
AC |
5 ms |
4352 KB |
19.txt |
AC |
5 ms |
4352 KB |
20.txt |
AC |
5 ms |
4352 KB |
21.txt |
AC |
5 ms |
4352 KB |
22.txt |
AC |
5 ms |
4352 KB |
23.txt |
AC |
4 ms |
4352 KB |
24.txt |
AC |
5 ms |
4352 KB |
25.txt |
AC |
5 ms |
4352 KB |
26.txt |
AC |
5 ms |
4352 KB |
27.txt |
AC |
5 ms |
4352 KB |
28.txt |
AC |
5 ms |
4352 KB |
29.txt |
AC |
5 ms |
4352 KB |
30.txt |
AC |
5 ms |
4352 KB |
31.txt |
AC |
5 ms |
4352 KB |
32.txt |
AC |
5 ms |
4352 KB |
33.txt |
AC |
5 ms |
4352 KB |
34.txt |
AC |
4 ms |
4352 KB |
35.txt |
AC |
5 ms |
4352 KB |
36.txt |
AC |
4 ms |
4352 KB |
37.txt |
AC |
4 ms |
4352 KB |
38.txt |
AC |
4 ms |
4352 KB |
39.txt |
AC |
6 ms |
4480 KB |
40.txt |
AC |
4 ms |
4352 KB |
41.txt |
AC |
4 ms |
4352 KB |
42.txt |
AC |
3 ms |
3072 KB |
43.txt |
AC |
6 ms |
4480 KB |
44.txt |
AC |
6 ms |
4480 KB |
45.txt |
AC |
6 ms |
4480 KB |
46.txt |
AC |
6 ms |
4480 KB |
47.txt |
AC |
5 ms |
3200 KB |
48.txt |
AC |
5 ms |
3200 KB |
49.txt |
AC |
2 ms |
2304 KB |
50.txt |
AC |
2 ms |
2304 KB |
51.txt |
AC |
2 ms |
2304 KB |
52.txt |
AC |
2 ms |
2304 KB |
53.txt |
AC |
2 ms |
2304 KB |
54.txt |
AC |
2 ms |
2304 KB |
55.txt |
AC |
2 ms |
2304 KB |
56.txt |
AC |
2 ms |
2304 KB |
57.txt |
AC |
2 ms |
2304 KB |
58.txt |
AC |
2 ms |
2304 KB |
59.txt |
AC |
2 ms |
2304 KB |
60.txt |
AC |
2 ms |
2304 KB |
61.txt |
AC |
2 ms |
2304 KB |
62.txt |
AC |
2 ms |
2304 KB |
63.txt |
AC |
2 ms |
2304 KB |
64.txt |
AC |
2 ms |
2304 KB |
s1.txt |
AC |
2 ms |
2304 KB |
s2.txt |
AC |
2 ms |
2304 KB |
s3.txt |
AC |
1 ms |
2304 KB |
s4.txt |
AC |
2 ms |
2304 KB |