Submission #1569547

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;
#define MOD 1000000007

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    long long A, B;
    cin >> N >> A >> B;
    vector<long long> S(N+1);
    S[0] = -(1LL << 60);
    for(int i=1; i<=N; i++) cin >> S[i];
    if(A > B) swap(A, B);
    for(int i=2; i<=N; i++)
        if(S[i] - S[i-2] < A){
            cout << 0 << endl;
            return 0;
        }

    vector<long long> dp1(N+1, 0), dp2(N+1, 0);
    dp1[0] = 1;
    dp2[0] = 1;
    int cur = 0;
    int tail = 0;
    for(int i=1; i<=N; i++){
        for(int j=cur; j<i; j++){
            if(S[i] - S[j] >= B){
                cur = j;
            }else break;
        }

        if(S[i] - S[i-1] < A){
            dp2[i-1] = dp1[i-1];
            int id = min(i-2, cur);
            if(tail <= id) dp1[i] = dp2[id];
            tail = i-1;
        }else if(tail <= cur){
            dp1[i] = dp2[cur];
        }
        dp2[i] = (dp2[i-1] + dp1[i]) % MOD;
    }

    long long ans = 0;
    for(int i=tail; i<=N; i++)
        ans += dp1[i];
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result