AtCoder Beginner Contest 327F問題

ABC327F

解法

リンゴを固定して，それを覆う籠の位置を動かす． 籠の左上や右上を，籠の位置と一対一対応させる．
縦軸を時刻，横軸を座標として 2次元で考える． リンゴ1個に対して，籠の範囲を考えると， 長方形領域が対応する． つまり，長方形領域(2次元)のグリッドに +1をして， 一番大きい数字が答え．

実装

愚直に行うと， 時刻: 2e5, 座標: 4e5 となり，MLT かつ TLE. そこで，座標だけ全探索して，時刻を高速に処理する．
座標を固定すると，時刻に対しては， 区間(1次元)に +1 をすることになる． これは，lazy_segtree で実装できる．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

struct Event{

  ll l, r, val;

  Event(){}

  Event(ll l, ll r, ll val) : l(l), r(r), val(val){}

};

ll op(ll a, ll b) {return max(a,b);}

ll e() {return 0;}

ll mapping (ll f, ll x) {return x += f; }

ll composition(ll f, ll g) {return f+g;}

ll id() { return 0; }

int main() {

  ll n, d, w;

  cin >> n >> d >> w;

  const ll MT = (ll)4e5 + 5;

  vector<vector<Event>> events(MT);

  rep(i,n){

    ll t,x; cin >> t >> x;

    events[t].emplace_back(x,x+w,+1);

    events[t+d].emplace_back(x,x+w,-1);

  }

  lazy_segtree<ll,op,e,ll,mapping,composition,id> seg(MT);

  ll ans = 0;

  rep(t, MT){

    for(auto ev: events[t]){

      seg.apply(ev.l, ev.r, ev.val);

    }

    chmax(ans, seg.all_prod());

  }

  cout << ans << endl;

  return 0;

}