Submission #3428249
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]-(l?sum[l-1][1]:0)+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]-(l?sum[l-1][0]: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
Submission Time |
|
Task |
A - Multiple Array |
User |
litble |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1488 Byte |
Status |
WA |
Exec Time |
2107 ms |
Memory |
16256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.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, s1.txt, s2.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
WA |
41 ms |
16256 KB |
02.txt |
WA |
32 ms |
15488 KB |
03.txt |
WA |
29 ms |
15488 KB |
04.txt |
WA |
43 ms |
16256 KB |
05.txt |
WA |
30 ms |
15488 KB |
06.txt |
WA |
30 ms |
15488 KB |
07.txt |
AC |
31 ms |
16256 KB |
08.txt |
WA |
34 ms |
15488 KB |
09.txt |
AC |
37 ms |
16256 KB |
10.txt |
WA |
36 ms |
15488 KB |
11.txt |
WA |
31 ms |
16256 KB |
12.txt |
AC |
31 ms |
16256 KB |
13.txt |
WA |
27 ms |
16256 KB |
14.txt |
AC |
28 ms |
15488 KB |
15.txt |
TLE |
2107 ms |
2304 KB |
16.txt |
TLE |
2103 ms |
2304 KB |
s1.txt |
WA |
1 ms |
2304 KB |
s2.txt |
WA |
1 ms |
2304 KB |