Submission #1110743

---

Source Code Expand

#include <bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
#define lc (x << 1)
#define rc (x << 1 | 1)
using namespace std;

template<class T> inline
void read(T& x) {
	int f = 1; x = 0;
	char ch = getchar();

	while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}

/*============ Header Template ============*/

const int N = 100000 + 5;
const int mo = 1000000007;

int n;
LL A, B;
LL s[N];

struct Segment_Tree {
	int sum[N << 2];
	int tag[N << 2];

	Segment_Tree() {
		memset(sum, 0, sizeof sum);
		memset(tag, 0, sizeof tag);
	}

	void upd(int x) {sum[x] = (sum[lc] + sum[rc]) % mo;}

	void make_tag(int x) {
		sum[x] = 0;
		tag[x] = 1;
	}

	void push_down(int x) {
		if (tag[x]) {
			make_tag(lc);
			make_tag(rc);
			tag[x] = 0;
		}
	}

	void reset() {make_tag(1);}

	void set(int x, int l, int r, int pos, int val) {
		if (l == r) {sum[x] = val; return;}
		push_down(x);
		int m = (l + r) >> 1;
		if (pos <= m) set(lc, l, m, pos, val);
		else set(rc, m + 1, r, pos, val);
		upd(x);
	}

	LL getsum(int x, int l, int r, int s, int t) {
		if (s <= l && r <= t) return sum[x];
		push_down(x);
		int m = (l + r) >> 1, ans = 0;
		if (s <= m) (ans += getsum(lc, l, m, s, t)) %= mo;
		if (m < t) (ans += getsum(rc, m + 1, r, s, t)) %= mo;
		return ans;
	}
} T1, T2;

int main() {
	read(n), read(A), read(B);
	for (int i = 1; i <= n; i++) read(s[i]);
	T1.set(1, 0, n, 0, 1);
	T2.set(1, 0, n, 0, 1);
	s[0] = -INF;
	int flagA0, flagB0;
	int la = 0, lb = 0;
	for (int i = 1; i <= n; i++) {
		flagA0 = flagB0 = 0;
		if (s[i] - s[i - 1] < A) flagA0 = 1;
		if (s[i] - s[i - 1] < B) flagB0 = 1;
		while (la + 1 <= i && s[i] - s[la + 1] >= A) la++;
		while (lb + 1 <= i && s[i] - s[lb + 1] >= B) lb++;
		int tmpA = T2.getsum(1, 0, n, 0, la);
		int tmpB = T1.getsum(1, 0, n, 0, lb);
		if (flagA0) T1.reset();
		if (flagB0) T2.reset();
		T1.set(1, 0, n, i - 1, tmpA);
		T2.set(1, 0, n, i - 1, tmpB);
	}
	int ans = (T1.getsum(1, 0, n, 0, n) + T2.getsum(1, 0, n, 0, n)) % mo;
	printf("%d\n", (ans + mo) % mo);
	return 0;
}

Submission Info

Judge Result