Submission #1628697
Source Code Expand
#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > >
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define SZ(x) ((int)x.size())
using namespace std;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
const int BufferSize=1<<16;
char buffer[BufferSize],*Bufferhead,*Buffertail;
bool Terminal;
inline char Getchar(){
if(Bufferhead==Buffertail){
int l=fread(buffer,1,BufferSize,stdin);
if(!l){Terminal=1;return 0;}
Buffertail=(Bufferhead=buffer)+l;
}
return *Bufferhead++;
}
template<class T>inline bool read(T &x){
x=0;char c=Getchar(),rev=0;
while(c<'0'||c>'9'){c=Getchar();rev|=c=='-';if(Terminal)return 0;}
while(c>='0'&&c<='9') x=x*10+c-'0',c=Getchar();
if(c=='.'){
c=Getchar();double t=0.1;
while(c>='0'&&c<='9') x=x+(c-'0')*t,c=Getchar(),t=t/10;
}
x=rev?-x:x;
return 1;
}
template<class T1,class T2> inline bool read(T1 &x,T2 &y){return read(x)&read(y);}
template<class T1,class T2,class T3> inline bool read(T1 &x,T2 &y,T3 &z){return read(x)&read(y)&read(z);}
template<class T1,class T2,class T3,class T4> inline bool read(T1 &x,T2 &y,T3 &z,T4 &w){return read(x)&read(y)&read(z)&read(w);}
inline bool reads(char *x){
char c=Getchar();
while(c<33||c>126){c=Getchar();if(Terminal)return 0;}
while(c>=33&&c<=126) (*x++)=c,c=Getchar();
*x=0;return 1;
}
template<class T>inline void print(T x,const char c='\n'){
if(!x){putchar('0');putchar(c);return;}
if(x<0) putchar('-'),x=-x;
int m=0,a[20];
while(x) a[m++]=x%10,x/=10;
while(m--) putchar(a[m]+'0');
putchar(c);
}
//--------------------------------------------------head--------------------------------------------------
const int inf=0x3f3f3f3f;
const int N=200005,M=100005,mod=1e9+7;
template<class T,class S> inline void ch(T &x,const S y){x=(x+y)%mod;}
inline int exp(int x,int y,const int mod=::mod){
int ans=1;
while(y){
if(y&1) ans=(ll)ans*x%mod;
x=(ll)x*x%mod;y>>=1;
}return ans;
}
int n,dp1[N],dp2[N],s1[N],s2[N];
ll A,B,a[N];
int main(){
#ifdef rqgao2014
freopen("input.txt","r",stdin);
#endif
read(n,A,B);
for(int i=1;i<=n;i++) read(a[i]);
a[0]=-inf;
dp1[0]=dp2[0]=1;
s1[0]=s2[0]=1;
int l=0,r=0;
for(int i=2,xx=0,yy=0;i<=n;i++){
while(xx<n&&a[i]-a[xx+1]>=A) xx++;
while(yy<n&&a[i]-a[yy+1]>=B) yy++;
// dprintf("%d %d\n",xx,yy);
dp1[i-1]=s2[min(xx,i-2)];s1[i-1]=(s1[i-2]+dp1[i-1])%mod;
dp2[i-1]=s1[min(yy,i-2)];s2[i-1]=(s2[i-2]+dp2[i-1])%mod;
if(a[i]-a[i-1]<A){
for(int j=l;j<=i-2;j++)
dp1[j]=0,s1[j]=0;
s1[i-1]=dp1[i-1];l=i-1;
}
if(a[i]-a[i-1]<B){
for(int j=r;j<=i-2;j++)
dp2[j]=0,s2[j]=0;
s2[i-1]=dp2[i-1];r=i-1;
}
// dprintf("%d %d\n",l,r);
// for(int j=0;j<n;j++) dprintf("%d ",dp1[j]);puts("");
// for(int j=0;j<n;j++) dprintf("%d ",dp2[j]);puts("\n");
}
// for(int i=l;i<n;i++) dprintf("%d ",dp1[i]);puts("");
print((s1[n-1]+s2[n-1])%mod);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Division into Two |
User |
rqgao2014 |
Language |
C++14 (GCC 5.4.1) |
Score |
1100 |
Code Size |
3631 Byte |
Status |
AC |
Exec Time |
8 ms |
Memory |
3712 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 |
8 ms |
3712 KB |
02.txt |
AC |
7 ms |
3712 KB |
03.txt |
AC |
7 ms |
3712 KB |
04.txt |
AC |
7 ms |
3712 KB |
05.txt |
AC |
7 ms |
3712 KB |
06.txt |
AC |
7 ms |
3712 KB |
07.txt |
AC |
8 ms |
3712 KB |
08.txt |
AC |
8 ms |
3712 KB |
09.txt |
AC |
8 ms |
3712 KB |
10.txt |
AC |
8 ms |
3712 KB |
11.txt |
AC |
7 ms |
3712 KB |
12.txt |
AC |
7 ms |
3712 KB |
13.txt |
AC |
7 ms |
3712 KB |
14.txt |
AC |
8 ms |
3712 KB |
15.txt |
AC |
7 ms |
3712 KB |
16.txt |
AC |
4 ms |
3712 KB |
17.txt |
AC |
5 ms |
3712 KB |
18.txt |
AC |
6 ms |
3712 KB |
19.txt |
AC |
5 ms |
3712 KB |
20.txt |
AC |
6 ms |
3712 KB |
21.txt |
AC |
6 ms |
3712 KB |
22.txt |
AC |
6 ms |
3712 KB |
23.txt |
AC |
5 ms |
3712 KB |
24.txt |
AC |
6 ms |
3712 KB |
25.txt |
AC |
7 ms |
3712 KB |
26.txt |
AC |
6 ms |
3712 KB |
27.txt |
AC |
7 ms |
3712 KB |
28.txt |
AC |
7 ms |
3712 KB |
29.txt |
AC |
6 ms |
3712 KB |
30.txt |
AC |
6 ms |
3712 KB |
31.txt |
AC |
6 ms |
3712 KB |
32.txt |
AC |
6 ms |
3712 KB |
33.txt |
AC |
7 ms |
3712 KB |
34.txt |
AC |
5 ms |
3712 KB |
35.txt |
AC |
7 ms |
3712 KB |
36.txt |
AC |
4 ms |
3712 KB |
37.txt |
AC |
4 ms |
3712 KB |
38.txt |
AC |
4 ms |
3712 KB |
39.txt |
AC |
7 ms |
3712 KB |
40.txt |
AC |
5 ms |
3712 KB |
41.txt |
AC |
5 ms |
3712 KB |
42.txt |
AC |
4 ms |
3712 KB |
43.txt |
AC |
7 ms |
3712 KB |
44.txt |
AC |
7 ms |
3712 KB |
45.txt |
AC |
7 ms |
3712 KB |
46.txt |
AC |
7 ms |
3712 KB |
47.txt |
AC |
8 ms |
3712 KB |
48.txt |
AC |
8 ms |
3712 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 |
1 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 |
1 ms |
2304 KB |
s1.txt |
AC |
2 ms |
2304 KB |
s2.txt |
AC |
2 ms |
2304 KB |
s3.txt |
AC |
2 ms |
2304 KB |
s4.txt |
AC |
2 ms |
2304 KB |