$O(2^n \cdot n)$ solution:

Go through all possible subsets and check if every camper has a coach within $D$ units to the left.

$O(n^2)$ solution:

$dp_{i,j}$: we are at $i$, $j$ is the last coach that got chosen.

If $i$ is a coach: $dp_{i,j}$ = $dp_{i-1,j-1}$ + $dp_{i-1,j-2}$ + $\ldots$ + $dp_{i-1,0}$

If $i$ is a camper: $dp_{i,j}$ = $dp_{i-1,j} \cdot$ (1 + ($dis(i, j) \leq D$))

Eva's code:

#include <bits/stdc++.h>
#define ll long long
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, b, a) for(int i = (b); i >= (a); i--)
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
ll D, p[N], dp[N], ndp[N], total;
int n, o[N];
int main() {
    scanf("%d%lld", &n, &D);
    rep(i, 1, n) scanf("%lld%d", &p[i], &o[i]);
    dp[0] = 1;
    rep(i, 1, n) dp[i] = 0;
    rep(i, 1, n) {
        rep(j, 0, i) ndp[j] = 0;
        if (o[i] == 1) {
            ll sum = 0;
            rep(j, 0, i-1) sum = (sum + dp[j]) % MOD;
            rep(j, 0, i-1) ndp[j] = dp[j];
            ndp[i] = sum;
        } 
        else {
            rep(j, 0, i - 1) {
                ll val = dp[j];
                if (j > 0 && p[i] - p[j] <= D) {
                    val = (val * 2) % MOD;
                }
                ndp[j] = val;
            }
            ndp[i] = 0;
        }
        rep(j, 0, i) dp[j] = ndp[j];
    }
    rep(j, 0, n) total = (total + dp[j]) % MOD;
    printf("%lld\n", (total - 1 + MOD) % MOD);
    return 0;
}

$O(n)$ solution:

For a camper at index $i$ to be selectable, we need some selected coach in positions $[p_i-D, p_i)$. Only the rightmost coach among these matters, so states should be about rightmost coaches.

Let $f_j$ be the number of good subsets (within the processed prefix) whose rightmost selected coach is exactly $j$.

If current $i$ is a camper: For all eligible coach-states $c$ in range, $f_c$ doubles (choose or not choose this camper); other $f_c$ remain the same.

If current $i$ is a coach: $f_i$ = $TOTAL$ (all possible subsets until now since $i$ can be chosen or not). An $O(n\log n)$ solution would be using a segment tree to maintain this. However, we can also use a queue to maintain a sliding window and get an $O(n)$ solution.

Maintain a queue of the current active coaches. Maintain $mul$ which starts with $1$.

Every time, instead of doubling all the $f$ for current active coaches, let $mul \mathrel{*}= 2$.

Maintain an array $g$, such that $f_i$ = $g_i \cdot mul$. Also maintain the sum of $g$.

To conclude, we maintain:

$mul$ representing the "lazy tag" for the current queue.

$fsum$ = sum of $f_i$ for coaches already popped (inactive; never changes again).

$gsum$ = sum of $g_i$ for coaches still active.

$s$ = $gsum \cdot mul$

$TOTAL$ = $1$ (empty) + $fsum$ + $s$

Eva's code:

#include <bits/stdc++.h>
#define ll long long
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, b, a) for(int i = (b); i >= (a); i--)
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
ll p, D, inv2 = (MOD + 1) / 2, qp[N], qg[N];
int main() {
    int n; scanf("%d%lld", &n, &D);
    ll mul = 1, inv_mul = 1, fsum = 0, gsum = 0;
    int headp = 1, tailp = 0;
    int headg = 1, tailg = 0;
    rep(i, 1, n){
        int o; scanf("%lld%d", &p, &o);
        while(headp <= tailp && qp[headp] < p-D){
            fsum = (fsum + (qg[headg] * mul)) % MOD;
            gsum = (gsum - qg[headg]) % MOD;
            headp++, headg++;
        }
        if(o == 0){
            mul = (mul * 2) % MOD;
            inv_mul = (inv_mul * inv2) % MOD;
        } 
        else{
            ll total = (1 + fsum + gsum * mul % MOD) % MOD;
            ll x = (total * inv_mul) % MOD;
            qp[++tailp] = p, qg[++tailg] = x;
            gsum = (gsum + x) % MOD;
        }
    }
    ll ans = (fsum + (gsum * mul) % MOD) % MOD;
    printf("%lld\n", (ans + MOD) % MOD);
    return 0;
}