Submission #1776821

---

Source Code Expand

#include"bits/stdc++.h"


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = (l);x<=(u);x++)
#define RREP(x,l,u) for(ll x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 100010;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n;

ll A,B,S[maxn];

int sm[maxn*42],ls[maxn*42],rs[maxn*42],sz;

int f[maxn],g[maxn];

void update(int x,int& y,int l,int r,int t,int v){
	if(t<0||t>n)return;
	sm[y=++sz]=(sm[x]+v)%mod;ls[y]=ls[x];rs[y]=rs[x];
	if(l==r)return;
	int M=l+r>>1;
	if(t<=M)update(ls[x],ls[y],l,M,t,v);else update(rs[x],rs[y],M+1,r,t,v);
}

int query(int x,int l,int r,int L,int R){
	if(L>R)return 0;
	if(!x)return 0;
	if(L<=l&&r<=R)return sm[x];
	int M=l+r>>1,ans=0;
	if(L<=M)ans=query(ls[x],l,M,L,R);
	if(r>M)ans=(ans+query(rs[x],M+1,r,L,R))%mod;
	return ans;
}

void Work(){
	update(f[1],f[1],0,n,0,1);update(g[1],g[1],0,n,0,1);
	REP(i,2,n){
		if(S[i]-S[i-1]>=A)f[i]=f[i-1];
		if(S[i]-S[i-1]>=B)g[i]=g[i-1];
		int x;
		x=upper_bound(S+1,S+n+1,S[i]-A)-S-1;
		update(f[i],f[i],0,n,i-1,query(g[i-1],0,n,0,x));
		x=upper_bound(S+1,S+n+1,S[i]-B)-S-1;
		update(g[i],g[i],0,n,i-1,query(f[i-1],0,n,0,x));
	}
	int ans=(query(f[n],0,n,0,n)+query(g[n],0,n,0,n))%mod;
	iout(ans);
}

void Init(){
	read(n,A,B);
	REP(i,1,n)read(S[i]);
}

int main(){
	Init();
	Work();
	return 0;
}

Submission Info

Judge Result