問題ページ
考えたこと
- 集合を2分割する系なのでDPを考える
- 集合に入っている要素のうち一番大きい要素が大事
- 集合が空のときを考えるのは面倒なのでX,Yには-infが入っているものとしておく
- dp[i][j] = (集合にs[i]まで挿入していて、Yに最後に入れた要素がs[j]) としてみる
- この2乗DPをうまいこと高速化するみたいな方針で考えた
- このdpの遷移を考える
- j<iのときはs[i]を集合Xに追加していて、j=iのときはs[i]を集合Yに追加している
- 集合Xに追加する場合はXの最大の要素とs[i]を比較し差がA以上かで追加可能か場合分けでき dp[i][j] = dp[i-1][j] or 0 となる
- 集合Yに追加する場合は差分の条件を満たすものの和となり dp[i][j] = sum(dp[i-1][k], s[i]-s[k]>=B) となる
- 条件を満たすkには単調性があるので二分探索でkの位置は求めることができ、累積和かセグ木等を使えば区間和は高速に求められる
- 集合Xに追加する場合を愚直に書くと遷移にO(N)かかって当然TLE
- dpテーブルをにらんで高速化を考える
- s[i] - s[i-1] >= A であれば dp[i][j] = dp[i-1][j] となって 0 と更新される場所はない
- 問題は s[i] - s[i-1] < A のとき
- このとき X に s[i-1] が追加されているとs[i]を追加することはできない
- dp[i][j] (j <= i-2) ではXにs[i-1]が追加されているためこれは不可能で0になる
- dp[i][i-1] はどうなるか?
- s[i] - s[i-2] >= A であれば嬉しくて集合Xの最大がs[i-2]、集合Yの最大がs[i-1]の状況でもXにs[i]を突っ込める
- つまりdp[i][i-1] = dp[i-1][i-1] と書ける
- s[i] - s[i-2] < A だと集合Xの最大がs[i-2]のケースにs[i]を突っ込めなくて面倒そう
- 冷静になって考えると s[i] - s[i-2] < A だとどう頑張っても集合に要素を入れられない
- ↑(A > B だと集合に要素を入れられるがこれはswap(A,B)すればよいだけなので A<=B として考えてよい)
- なのでこれがあったら最初に0を出力して終了してよい
- dpの遷移が定数個の区間更新と区間和を求めるクエリで書けそうなことがわかった
- これは遅延セグ木で実現できるのでDPをO(NlogN)で書ける
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using PII = pair<int, int>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;
template <typename T, typename E>
struct lazySegTree {
using F = function<T(T,T)>;
using G = function<T(T,E)>;
using H = function<E(E,E)>;
using P = function<E(E,int)>;
F f; G g; H h; P p; T d1; E d0;
int n;
vector<T> dat;
vector<E> lazy;
lazySegTree(){}
lazySegTree(int n_, F f_, G g_, H h_,
T d1_, E d0_, P p_=[](E a, int b){return a;})
: f(f_), g(g_), h(h_), p(p_), d1(d1_), d0(d0_)
{
n = 1; while(n < n_) n *= 2;
dat.assign(n*2-1, d1);
lazy.assign(n*2-1, d0);
}
void build(vector<T> v) {
REP(i, v.size()) dat[i+n-1] = v[i];
for(int i=n-2; i>=0; --i) dat[i] = f(dat[i*2+1], dat[i*2+2]);
}
inline void eval(int len, int k) {
if(lazy[k] == d0) return;
if(k*2+1 < n*2-1) {
lazy[2*k+1] = h(lazy[k*2+1], lazy[k]);
lazy[2*k+2] = h(lazy[k*2+2], lazy[k]);
}
dat[k] = g(dat[k],p(lazy[k],len));
lazy[k] = d0;
}
T update(int a, int b, E x, int k, int l, int r) {
eval(r-l, k);
if(b <= l || r <= a) return dat[k];
if(a <= l && r <= b) {
lazy[k] = h(lazy[k], x);
return g(dat[k], p(lazy[k],r-l));
}
return dat[k] = f(update(a, b, x, 2*k+1, l, (l+r)/2),
update(a, b, x, 2*k+2, (l+r)/2, r));
}
T update(int a, int b, E x) { return update(a, b, x, 0, 0, n); }
T query(int a, int b, int k, int l, int r) {
eval(r-l, k);
if(a <= l && r <= b) return dat[k];
bool left = !((l+r)/2 <= a || b <= l), right = !(r <= 1 || b <= (l+r)/2);
if(left&&right) return f(query(a, b, 2*k+1, l, (l+r)/2), query(a, b, 2*k+2, (l+r)/2, r));
if(left) return query(a, b, 2*k+1, l, (l+r)/2);
return query(a, b, 2*k+2, (l+r)/2, r);
}
T query(int a, int b) { return query(a, b, 0, 0, n); }
void debug() {
REP(i, n) query(i, i+1);
cout << "---------------------" << endl;
int cnt = 0;
for(int i=1; i<=n; i*=2) {
REP(j, i) {
cout << "(" << dat[cnt] << "," << lazy[cnt] << ") ";
cnt++;
}
cout << endl;
}
cout << "---------------------" << endl;
}
};
signed main(void)
{
cin.tie(0);
ios::sync_with_stdio(false);
ll n, a, b;
cin >> n >> a >> b;
if(a > b) swap(a, b);
vector<ll> s(n+1); s[0] = -LLINF;
FOR(i, 1, n+1) cin >> s[i];
FOR(i, 2, n+1) {
if(s[i] - s[i-2] < a) {
cout << 0 << endl;
return 0;
}
}
auto f = [&](ll a, ll b){ return (a+b) % MOD; };
auto g = [&](ll a, ll b){ return b==-1?a:b; };
auto p = [&](ll a, int b){ return (a*b) % MOD; };
lazySegTree<ll, ll> seg(n+1, f, g, g, 0, -1, p);
seg.update(0, 1, 1);
FOR(i, 1, n+1) {
int lb = 0, ub = n+2;
while(ub - lb > 1) {
int mid = (lb+ub)/2;
if(s[mid] <= s[i] - b) lb = mid;
else ub = mid;
}
ll tmp = seg.query(0, lb+1);
seg.update(i, i+1, tmp);
if(s[i] - s[i-1] >= a) {
} else {
seg.update(0, i-1, 0);
}
}
cout << seg.query(0, n+2) % MOD << endl;
return 0;
}
