Submission #1319881

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Mod
{
    static const int P = int(1e9+7);
    int k;

    Mod() = default;
    Mod(const int k) : k(k%P) {}
};

Mod operator+(const Mod a, const Mod b) { return a.k + b.k; }
Mod operator-(const Mod a) { return -a.k + Mod::P; }
Mod& operator+=(Mod& a, const Mod b) { return a = a+b; }

struct FenwickTree
{
    int N;
    vector<Mod> data;
    vector<pair<int, Mod>> modifications;

    FenwickTree(const int N) : N(N), data(N+1) {}

    void add(const int n, const Mod x, const bool track = true)
    {
        if (track) modifications.push_back({n, x});
        for (int i = n+1; i <= N; i += i & -i)
            data[i] += x;
    }

    Mod query(const int n)
    {
        Mod result(0);
        for (int i = n+1; i >= 1; i -= i & -i)
            result += data[i];
        return result;
    }

    void clear()
    {
        for (const auto m : modifications)
            add(m.first, -m.second, false);
        modifications.clear();
    }
};

int main()
{
    int N; ll A, B; cin >> N >> A >> B;

    vector<ll> S(N+1);
    S[0] = numeric_limits<ll>::min();
    for (int i = 1; i <= N; i++)
        cin >> S[i];

    const auto search = [&](const ll x)
    {
        return int(upper_bound(begin(S), end(S), x) - begin(S)) - 1;
    };

    FenwickTree X(N), Y(N);
    X.add(0, 1); Y.add(0, 1);
    for (int i = 2; i <= N; i++)
    {
        const Mod y = X.query(search(S[i]-B));
        const Mod x = Y.query(search(S[i]-A));

        if (S[i]-S[i-1] < A) X.clear();
        if (S[i]-S[i-1] < B) Y.clear();

        X.add(i-1, x);
        Y.add(i-1, y);
    }
    cout << (X.query(N-1) + Y.query(N-1)).k << endl;
}

Submission Info

Judge Result