Submission #1774984

---

Source Code Expand

#include <bits/stdc++.h>
#define lsb(x) ((x) & -(x))
#define MOD 1000000007
using namespace std;

const int NMAX = 100010;

inline void add(int & a, int b)
{
    a += b;
    if (a >= MOD)
        a -= MOD;
}
class Aib
{
    vector <int> pozitii;
    vector <int> aib;
public:
    Aib() {
        aib = vector <int> (NMAX + 5);
    }
    void update(int val, int poz)
    {
        poz++;
        while (poz <= NMAX) {
            if (aib[poz] == 0)
                pozitii.push_back(poz);
            add(aib[poz], val);
            poz += lsb(poz);
        }
    }
    int query(int poz)
    {
        poz++;
        int ans(0);
        while (poz) {
            add(ans, aib[poz]);
            poz -= lsb(poz);
        }
        return ans;
    }
    void clear()
    {
        for (auto i : pozitii)
            aib[i] = 0;
        pozitii.clear();
    }
};

Aib aib[2];

int s[100010];
int dif[2];

int pozmax(int x, int dif)
{ /// poztia maxima a.i. s[x] - s[max] >= dif
    int p(0), q(1 << 20);
    while (q >>= 1)
        if (p + q < x && s[x] - s[p + q] >= dif)
            p += q;
    return p;
}

void tranz(int x)
{
    int updates[2];
    for (int i(0); i <= 1; i++) {
        updates[1 - i] = aib[i].query(pozmax(x + 1,  dif[1 - i]));
        if (s[x + 1] - s[x] < dif[i])
            aib[i].clear();
    }
    for (int i(0); i <= 1; i++)
        aib[i].update(updates[i], x);
}

//int dp[2][10][10];


int main()
{
    int n;
    cin >> n >> dif[0] >> dif[1];

    for (int i(1); i <= n; i++)
        cin >> s[i];

    aib[0].update(1, 0);
    aib[1].update(1, 0);

    /*for (int q(0); q <= 1; q++) {
        for (int j(0); j <= n; j++) {
            dp[q][1][j] = aib[q].query(j) - aib[q].query(j - 1);
        }
    }*/

    for (int i(1); i < n; i++) {
        tranz(i);
        /*for (int q(0); q <= 1; q++) {
            for (int j(0); j <= n; j++) {
                dp[q][i + 1][j] = aib[q].query(j) - aib[q].query(j - 1);
            }
        }
    }

    for (int q(0); q <= 1; q++) {
        for (int i(1); i <= n; i++) {
            for (int j(0); j <= n; j++) {
                cout << dp[q][i][j] << " \n"[j == n];
            }
        }
        cout << '\n';*/
    }

    cout << (aib[0].query(n) + aib[1].query(n)) % MOD;
    return 0;
}

Submission Info

Judge Result