Submission #4570489

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dat[1000000];
ll u;
ll inf=1000000000000000001;
ll mod=1000000007;
void add(ll n,ll x){
  ll i=n+u-1;
  dat[i]=x;
  while(i>0){
    i=(i-1)/2;
    dat[i]=min(dat[2*i+1],dat[2*i+2]);
  }
}
ll que(ll a,ll b,ll k,ll l,ll r){
  if(a>=r||b<=l)return inf;
  if(a<=l&&b>=r)return dat[k];
  ll m1=que(a,b,2*k+1,l,(l+r)/2);
  ll m2=que(a,b,2*k+2,(l+r)/2,r);
  return min(m1,m2);
}
int main(){
  fill(dat,dat+1000000,inf);
  ll n,a,b;cin>>n>>a>>b;
  vector<ll> s(n);
  for(ll i=0;i<n;i++)cin>>s[i];
  for(ll i=0;;i++){
    ll e=pow(2,i);
    if(e>=n-1){
      u=e;
      break;
    }
  }
  for(ll i=0;i<n-1;i++){
    add(i,s[i+1]-s[i]);
  }
  ll dp1[n],dp2[n];
  fill(dp1,dp1+n,0);
  fill(dp2,dp2+n,0);
  dp1[0]=1;
  dp2[0]=1;
  for(ll i=1;i<n;i++){
    ll t=upper_bound(s.begin(),s.end(),s[i]-a)-s.begin();
    if(t==0){
      if(i==1){
        dp1[i]=1;
      }
      else{
        ll r=que(0,i-1,0,0,u);
        if(r>=b)dp1[i]=1;
      }
    }
    else{
      if(t==i){
        dp1[i]+=dp1[t-1]+dp2[t-1];
        dp1[i]%=mod;
      }
      else if(t==i-1){
        dp1[i]+=dp1[t-1];
        dp1[i]%=mod;
        if(s[i-1]-s[i-2]>=b)dp1[i]+=dp2[t-1];
        dp1[i]%=mod;
      }
      else{
        ll f=que(t-1,i-1,0,0,u);
        ll g=que(t,i-1,0,0,u);
        if(f>=b)dp1[i]+=dp2[t-1];
        dp1[i]%=mod;
        if(g>=b)dp1[i]+=dp1[t-1];
        dp1[i]%=mod;
      }
    }
    ll tt=upper_bound(s.begin(),s.end(),s[i]-b)-s.begin();
    //if(i==3)cout<<tt<<endl;
    if(tt==0){
      if(i==1){
        dp2[i]=1;
      }
      else{
        ll r=que(0,i-1,0,0,u);
        if(r>=b)dp2[i]=1;
      }
    }
    else{
      if(tt==i){
        dp2[i]+=dp1[tt-1]+dp2[tt-1];
        dp2[i]%=mod;
      }
      else if(tt==i-1){
        dp2[i]+=dp2[tt-1];
        dp2[i]%=mod;
        if(s[i-1]-s[i-2]>=a)dp2[i]+=dp1[tt-1];
        dp2[i]%=mod;
      }
      else{
        ll f=que(tt-1,i-1,0,0,u);
        ll g=que(tt,i-1,0,0,u);
        if(f>=a)dp2[i]+=dp1[tt-1];
        dp2[i]%=mod;
        if(g>=a)dp2[i]+=dp2[tt-1];
        dp2[i]%=mod;
      }
    }
  }
 
  ll ans=dp1[n-1]+dp2[n-1];
  cout<<ans%mod<<endl;
}

Submission Info

Judge Result