Submission #5499330

---

Source Code Expand

#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

//#include <cv.h>
//#include <highgui.h>
#include <stdlib.h>
#include <time.h>

#include <string>

class BIT {
    // Binary Indexed Tree : 数列要素1つへの加算、数列のある地点までの累積和を高速に計算
    public:
    std::vector<long long> data;
    BIT() {}
    BIT(const int size) {
        // 想定されるサイズの2倍の値を入れた方がいいかもしれない。数列は1から数えることを想定している。
        data.resize(size, 0);
    }
    long long sum(int i) const {
        long long s = 0;
        while (i > 0) {
            s += data[i];
            i = i & (i-1); // iの最後のビットを引く。
        }
        return s;
    }

    long long sum_mod(int i, long long mod) const {
        long long s = 0;
        while (i > 0) {
            s = (s + data[i] + mod) % mod;
            i = i & (i-1); // iの最後のビットを引く。
        }
        return s;
    }

    long long val(int i) const {
        if (i == 1) { return sum(i); }
        else {
            return sum(i) - sum(i-1);
        }
    }

    long long val_mod(int i, long long mod) const {
        if (i == 1) { return sum(i); }
        else {
            return (sum(i) - sum(i-1) + mod) % mod;
        }
    }

    void add(int i, long long x) {
        while (i < data.size()) {
            data[i] += x;
            i += i - (i & (i-1)); // iの最後のビットを加算する。
        }
    }

    void add_mod(int i, long long x, long long mod) {
        while (i < data.size()) {
            data[i] = (data[i] + x + mod) % mod;
            i += i - (i & (i-1)); // iの最後のビットを加算する。
        }
    }
};

class BIT2 {
    // Binary Indexed Tree 2つ : 数列区間への加算、数列のある地点までの累積和を高速に計算。
    public:
    BIT bit[2];
    BIT2() {}
    BIT2(const int size) {
        bit[0] = BIT(size);
        bit[1] = BIT(size);
    }
    long long sum(int i) const {
        return bit[1].sum(i) * i + bit[0].sum(i);
    }
    long long sum_mod(int i, long long mod) const {
        return (bit[1].sum_mod(i, mod) * i + bit[0].sum_mod(i, mod)) % mod;
    }
    long long val(int i) const {
        if (i == 1) { return sum(i); }
        else {
            return sum(i) - sum(i-1);
        }
    }
    long long val_mod(int i, long long mod) const {
        if (i == 1) { return sum_mod(i, mod); }
        else {
            return (sum_mod(i, mod) - sum_mod(i-1, mod) + mod) % mod;
        }
    }
    void add(int l, int r, long long x) {
        // [l,r]にxを加算。閉区間であり、rを含む点に注意。l=rの時、一つの値のみを操作できることになる。
        bit[0].add(l, -x * (l - 1));
        bit[1].add(l, x);
        bit[0].add(r + 1, x * r);
        bit[1].add(r + 1, -x);
    }
    void add_mod(int l, int r, long long x, long long mod) {
        // [l,r]にxを加算。閉区間であり、rを含む点に注意。l=rの時、一つの値のみを操作できることになる。
        bit[0].add_mod(l, -x * (l - 1), mod);
        bit[1].add_mod(l, x, mod);
        bit[0].add_mod(r + 1, x * r, mod);
        bit[1].add_mod(r + 1, -x, mod);
    }
};

const long long MOD = 1000000007;
const int MAX_N = 100050;
int N;
long long A, B;
long long S[MAX_N];

int rXf[MAX_N], rYf[MAX_N];
// 現在の要素をXにしたときに、どこまで連続でXにできるか。

int cX[MAX_N], cY[MAX_N];
// 現在の要素をXにしたときに、次どこに同じ要素をおけるか。

long long untilX[MAX_N] = {}; // 現在の要素をXにして次の要素をYにする場合の数。
long long untilY[MAX_N] = {}; 

BIT2 uX = BIT2(MAX_N);
BIT2 uY = BIT2(MAX_N);

int main(int argc, char **argv) {
    std::cin >> N >> A >> B;

    for (int i = 1; i <= N; i++) {
        std::cin >> S[i];
    }

    if (N == 1) {
        std::cout << 2 << std::endl;
        return 0;
    }

    S[N+1] = S[N] + std::max(A, B);

    rXf[N] = N; rYf[N] = N;
    for (int i = N - 1; 1 <= i; i--) {
        if (S[i] + A <= S[i+1]) {
            rXf[i] = rXf[i+1];
        } else {
            rXf[i] = i;
        }

        if (S[i] + B <= S[i+1]) {
            rYf[i] = rYf[i+1];
        } else {
            rYf[i] = i;
        }
    }

    cX[0] = 1;
    cY[0] = 1;
    int posX = 1;
    int posY = 1;
    for (int i = 1; i <= N; i++) {
        while (S[posX] < S[i] + A) {
            posX++;
        }
        cX[i] = posX;

        while (S[posY] < S[i] + B) {
            posY++;
        }
        cY[i] = posY;
    }

    uX.add_mod(1, rXf[1], 1, MOD);
    uY.add_mod(1, rYf[1], 1, MOD);

    for (int i = 2; i <= N; i++) {
        if (std::max(i, cY[i-1] - 1) <= rXf[i]) {
            uX.add_mod(std::max(i, cY[i-1] - 1), rXf[i], uY.val_mod(i-1, MOD), MOD);
        }
        if (std::max(i, cX[i-1] - 1) <= rYf[i]) {
            uY.add_mod(std::max(i, cX[i-1] - 1), rYf[i], uX.val_mod(i-1, MOD), MOD);
        }
    }

    std::cout << (uX.val_mod(N, MOD) + uY.val_mod(N, MOD)) % MOD << std::endl; 

    /*
    for (int j = 1; j <= rXf[1]; j++) {
        untilX[j] += 1;
    }
    for (int j = 1; j <= rYf[1]; j++) {
        untilY[j] += 1;
    }

    for (int i = 2; i <= N; i++) {
        for (int j = std::max(i, cY[i-1] - 1); j <= rXf[i]; j++) {
            untilX[j] += untilY[i-1];
        }
        for (int j = std::max(i, cX[i-1] - 1); j <= rYf[i]; j++) {
            untilY[j] += untilX[i-1];
        }
    }

    std::cout << untilX[N] + untilY[N] << std::endl;
    */
    
    return 0;
}

Submission Info

Judge Result