[ABC327] F - Apples

[Q} F - Apples

考察
1. y軸を時間、x軸を座標の位置として、2次元グラフでリンゴを書いてみる。

T
...o...o.o.o..
o.....o.......
...o.......o..
.oo...o..oo...
...o....oo..o.
.o.o..o.o.o..o X

2. D*Wの長方形を当てはめてみて、最もリンゴを囲める数はいくつ？が解答になる。
3. 時間でsortして、しゃくとり法で時間を進めていく。
4. 遅延セグ木にりんごのデータを入れて入れて・・・、時間を進めたら、Dにおさまらない分は出して出して・・・をする。
5. 都度、もっともリンゴのとれる値を更新。

実装

int main() {
  ll N, D, W;
  cin >> N >> D >> W;
  vector<pll> A;
  rep(i, N) {
    ll t, x;
    cin >> t >> x;
    A.emplace_back(t, x);
  }
  sort(all(A));

  // 遅延セグ木
  segment_tree seg(200020);

  // しゃくとり
  ll head = 0;
  ll ans = 0;
  rep(tail, N) {
    auto [t, x] = A[tail];
    while (head < N) { // 時間におさまらない限り取り出す
      auto [tt, xx] = A[head];
      if (t - tt >= D) {
        seg.update(max(0LL, xx - W + 1), min(200010LL, xx + 1), -1);
        ++head;
      } else
        break;
    }

    // リンゴを挿入
    seg.update(max(0LL, x - W + 1), min(200010LL, x + 1), 1); // update([L, R), addVal);
    chmax(ans, seg.range_max(0, 200001));
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/abc327/submissions/47268724