Submission #5023075

---

Source Code Expand

// And in the end, the love you take is equal to the love you make.
//                      Paul McCartney (the Beatles). The End. Abbey Road.

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

using LL = long long;

namespace _buff {

const size_t BUFF = 1 << 19;
char buff[BUFF], *begin = buff, *end = buff;
char getc() {
  if (begin == end) {
    begin = buff;
    end = buff + fread(buff, 1, BUFF, stdin);
  }
  return begin == end ? -1 : *begin++;
}

}

LL read() {
  using namespace _buff;
  LL ret = 0;
  bool pos = true;
  char c = getc();
  for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
    assert(~c);
  }
  if (c == '-') {
    pos = false;
    c = getc();
  }
  for (; c >= '0' && c <= '9'; c = getc()) {
    ret = (ret << 3) + (ret << 1) + (c ^ 48);
  }
  return pos ? ret : -ret;
}

const size_t N = 1e5 + 5;
const int MOD = 1e9 + 7;

int rmod(int x) {
  if (x >= MOD) x -= MOD;
  if (x  <  0 ) x += MOD;
  return x;
}

void add(int &dp, int val) {
  dp = rmod(dp + val);
}

int n; LL s[N], a, b;
int f[N], g[N], df[N], dg[N];
int suma[N], sumb[N];

bool calcfg(int j, int i) {
  return sumb[i] - sumb[j + 1] == 0;
}

bool calcgf(int j, int i) {
  return suma[i] - suma[j + 1] == 0;
}

int main() {
  n = read(); a = read(); b = read();
  generate_n(s + 1, n, read);
  s[0] = -2e18;
  s[n + 1] = 2e18;
  for (int i = 1; i <= n; ++i) {
    suma[i] = suma[i - 1] + (s[i] - s[i - 1] < a);
    sumb[i] = sumb[i - 1] + (s[i] - s[i - 1] < b);
  }
  f[0] = g[0] = 1;
  df[0] = dg[0] = 1;
  df[1] = dg[1] = MOD - 1;
  for (int i = 0; i <= n; ++i) {
    if (i) {
      add(df[i], df[i - 1]);
      add(dg[i], dg[i - 1]);
    }
    f[i] = df[i];
    g[i] = dg[i];
    if (i == n) break;
    /* calc f to g */ {
      static int l = 1, r = 1;
      while (s[l + 1] - s[i] < a) ++l;
      if (l <= i) l = i + 1;
      if (calcfg(i, l)) {
        if (r < l) r = l;
        while (r < n && calcfg(i, r + 1)) ++r;
        add(dg[l], f[i]);
        add(dg[r + 1], -f[i]);
      }
    } /* calc g to f */ {
      static int l = 1, r = 1;
      while (s[l + 1] - s[i] < b) ++l;
      if (l <= i) l = i + 1;
      if (calcgf(i, l)) {
        if (r < l) r = l;
        while (r < n && calcgf(i, r + 1)) ++r;
        add(df[l], g[i]);
        add(df[r + 1], -g[i]);
      }
    }
  }
  cout << rmod(f[n] + g[n]) << '\n';
  return 0;
}

Submission Info

Judge Result