https://agc009.contest.atcoder.jp/tasks/agc009_c
実家やるだけのはずなんですが通らないので後回しにします…。
int N; ll A, B; BIT bitx, bity; ll D[MAX_N]; const ll UB = 1e18; int cd(ll a) { return lower_bound(D, D + N, a) - D; } void solve() { cin >> N >> A >> B; D[0] = -4 * (UB + 1); D[1] = -2 * (UB + 1); rep(i, 0, N) cin >> D[i + 2]; N += 2; bitx.init(N); bity.init(N); bitx.update(0, 1, 1); rep(i, 2, N) { int xat = cd(D[i] - (B - 1)), yat = cd(D[i] - (A - 1)); ll vx = bity.get(boundy, yat), vy = bitx.get(boundx, xat); if(D[i] - D[i - 1] < A) boundx = i - 1; if(D[i] - D[i - 1] < B) boundy = i - 1; bitx.update(i - 1, i, vx); bity.update(i - 1, i, vy); // debug(i + 1, "x", bitx.show('x'), "y", bity.show('y'), boundx, boundy); } ll res = bitx.get(boundx, N) + bity.get(boundy, N); res %= mod; cout << res << "\n"; }