高橋君が正整数 \(S,L\) を選んでカゴを設置したとき、時刻 \(T_i\) に座標 \(X_i\) に落ちたリンゴを得るための必要十分条件は、\(\max(T_i-D+1,1)\leq S \leq T_i\) かつ\(\max(X_i-W+1,1)\leq L\leq X_i\) をみたすことです。これより、問題は次のように言い換えることができます。

無限に広がる \(tx\) 座標平面があり、\(t>0\) かつ \(x>0\) をみたす格子点 \((t,x)\) には最初 \(0\) が書き込まれています。
（格子点とは \(t,x\) 座標がともに整数であるような点のことです。）
\(N\) 回の操作を行います。 \(i\) 回目の操作では\(\max(T_i-D+1,1)\leq t \leq T_i\) かつ\(\max(X_i-W+1,1)\leq x\leq X_i\) をみたす格子点 \((t,x)\) に書かれている数を \(1\) 増加させます。
\(N\) 回の操作の後で、\(t>0\) かつ \(x>0\) の範囲の格子点に書き込まれている数のうち最大のものを求めてください。

この問題においては、\(N\) 回の操作の後で各格子点に書き込まれている数が、元の問題において高橋君が \(S,L\) を選んだ時に得られるリンゴの数に対応しています。

愚直にこの問題を解こうとすると、\(O(NDW)\) 程度の時間がかかり、制限時間内に実行することは困難です。
この問題は遅延セグメント木を用いて、高速に解くことができます。
ここで、制約から \(1\leq t\leq \max(T_i),1\leq x\leq \max(X_i)\) をみたす格子点 \((t,x)\) についてのみ考えれば十分である事に注意してください。

まず、\((1,x)\) \((1\leq x\leq \max(X_i))\) に書き込まれている数のうち最大のものを求める方法について考えます。
これは次のようにすれば良いです。
最初、全ての値が \(0\) であるような配列 \(A=(A_1,A_2,\ldots,A_{\max(X_i)})\) を用意します。
次に、 \(\max(T_i-D+1,1)\leq 1 \leq T_i\), すなわち \(T_i\leq D\) であるような操作について、\(A_x\) \((\max(X_i-W+1,1)\leq x\leq X_i)\) に \(1\) を加えます。 最後に \(A\) の要素の最大値を求めれば良いです。

次に \(t_0\geq 2\) について、\((t_0,x)\) \((1\leq x\leq 2\times 10^5)\) に書き込まれている数のうち最大のものを求める方法について考えます。 これは、\(t=t_0-1\) のときの配列を元に変更分を更新することによって求めることができます。更新する必要があるのは次の \(2\) つです。

• \(t-1<\max(T_i-D+1,1)\leq t\), すなわち \(T_i=t+D-1\) であるような操作について\(A_x\) \((\max(X_i-W+1,1)\leq x\leq X_i)\) を \(1\) 増加させる。

• \(t-1\leq T_i< t\), すなわち \(T_i=t-1\) であるような操作について\(A_x\) \((\max(X_i-W+1,1)\leq x\leq X_i)\) を \(1\) 減少させる。

これらの操作の後、 \(A\) の要素の最大値を求めることによって、\((t_0,x)\) \((1\leq x)\) に書き込まれている数のうち最大の値を得ることができます。

答えは、\(t_0=1,2,\ldots,2\times 10^5\) に対する、「 \((t_0,x)\) \((1\leq x)\) に書き込まれている数のうち最大のもの」のうち最大のものとして得ることができます。

さて、配列 \(A\) に対して行われているのは次の \(2\) つです。

• 配列の指定した範囲に特定の値を加える。(区間加算)
• 配列の指定した範囲(今回は配列全体のみ)における最大値を求める。(区間内最大値の取得)

これらの操作は遅延セグメント木によってどちらも \(O(\log |A|)\) (\(|A|\) は \(A\) の長さ\((=\max(X_i))\)) で行うことができます。配列に対する区間加算の回数は、各操作について高々 \(2\) 回であるため全体で高々 \(2N\) 回であり、最大値の取得は \(\max(T_i)\) 回 しか行われません。 よって、全体でかかる計算量は \(O((N+\max(T_i))\log(\max(X_i)))\) であり、十分高速です、

よって、この問題を解くことができました。

c++ による実装例:

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace std;
using namespace atcoder;

const int Tmax=(int)2e+5;
const int Xmax=(int)2e+5;

struct S {
    int x;
};

struct F {
    int x;
};

S op(S l, S r) { return S{max(l.x,r.x)}; }

S e() { return S{0}; }

S mapping(F l, S r) { return S{l.x+r.x}; }

F composition(F l, F r) { return F{l.x+r.x}; }

F id() { return F{0}; }

int main(void) {
	int n,d,w,t,x,ans=0;
	vector<pair<int,int> >q[Tmax+1];
	cin>>n>>d>>w;
	for(int i=0;i<n;i++){
		cin>>t>>x;
		q[max(t-d,0)].push_back({x,1});
		q[t].push_back({x,-1});
	}
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(Xmax);
    for(int i=0;i<Tmax;i++){
        int sz=q[i].size();
        for(int j=0;j<sz;j++){
            seg.apply(max(0,q[i][j].first-w),q[i][j].first,F{q[i][j].second});
        }
        ans=max(ans,seg.prod(0,Xmax).x);
    }
	cout<<ans<<endl;
	return 0;
}