Submission #1751614

---

Source Code Expand

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

typedef long long ll;
const int MAXN = 100010;
const ll MOD = 1000000007;

int n;
ll s[MAXN], A, B, ans;

template<typename T> inline T read() {
	T x(0), f(1);
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch=='-') f=-1;
	for(; isdigit(ch); ch = getchar()) x = (x*10)+(ch^48);
	return x * f;
}

inline void Update(ll &cur, ll val) {
	cur += val;
	if(cur >= MOD) cur -= MOD;
}

struct Seg_T {
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
	ll sum[MAXN*4], tag[MAXN*4];
	inline void pushdown(int p, int l, int r) {
		if(tag[p]) {
			tag[ls] = tag[rs] = tag[p];
			sum[ls] = tag[p]*l%MOD;
			sum[rs] = tag[p]*r%MOD;
			tag[p] = 0;
		}
	}
	inline void modify(int p, int l, int r, int x, int y, ll val) {
		if(l == x && r == y) {
			tag[p] = val;
			sum[p] = val*(y-x+1)%MOD;
			return;
		}
		pushdown(p, mid-l+1, r-mid);
		if(y <= mid) modify(ls, l, mid, x, y, val);
		else if(x > mid) modify(rs, mid+1, r, x, y, val);
		else {
			modify(ls, l, mid, x, mid, val);
			modify(rs, mid+1, r, mid+1, y, val);
		}
		sum[p] = (sum[ls]+sum[rs])%MOD;
	}
	inline ll query(int p, int l, int r, int x, int y) {
		if(l == x && r == y) return sum[p];
		pushdown(p, mid-l+1, r-mid);
		if(y <= mid) return query(ls, l, mid, x, y);
		if(x > mid) return query(rs, mid+1, r, x, y);
		return (query(ls, l, mid, x, mid)+query(rs, mid+1, r, mid+1, y))%MOD;
	}
}f, g;


int main() {

	int i, j;

	n = read<int>();
	A = read<ll>(), B = read<ll>();
	if(A > B) swap(A, B);
	for(i = 1; i <= n; i++) s[i] = read<ll>();

	f.modify(1, 1, n, 1, 1, 1);
	g.modify(1, 1, n, 1, 1, 1);
	/*for(i = 1; i <= n; i++) printf("%lld ", f.query(1, 1, n, i, i));
	printf("\n");
	for(i = 1; i <= n; i++) printf("%lld ", g.query(1, 1, n, i, i));
	printf("\n");*/
	for(i = 1; i < n; i++) {
		int loc = upper_bound(s+1, s+n+1, s[i+1]-B)-s-1;
		ll res = f.query(1, 1, n, 1, min(loc+1, i));
		//printf("%d:%lld ", loc, res);
		g.modify(1, 1, n, i+1, i+1, res);
		loc = upper_bound(s+1, s+n+1, s[i+1]-A)-s-1;
		res = g.query(1, 1, n, 1, min(loc+1, i));
		//printf("%d:%lld\n", loc, res);
		f.modify(1, 1, n, i+1, i+1, res);
		if(s[i+1]-s[i] < A) {
			f.modify(1, 1, n, 1, i, 0);
			//printf("fclear(%d, %d)\n", 1, i);
		}
		if(s[i+1]-s[i] < B) {
			g.modify(1, 1, n, 1, i, 0);
			//printf("gclear(%d, %d)\n", 1, i);
		}
	}
	Update(ans, f.query(1, 1, n, 1, n));
	Update(ans, g.query(1, 1, n, 1, n));
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Judge Result