103275: [Atcoder]ABC327 F - Apples

Problem Statement

There are apple trees lined up on a number line, and $N$ apples fall from the trees.
Specifically, for each $1\leq i\leq N$, an apple falls at coordinate $X_i$ at time $T_i$.

Takahashi has a basket with durability $D$ and length $W$, and he can take the following action exactly once.

Choose positive integers $S$ and $L$. He sets up the basket to cover the range $L-0.5\leq x\leq L+W-0.5$ at time $S-0.5$, and retrieves it at time $S+D-0.5$. He gets all the apples that fell into the range covered by the basket between the time it was set up and the time it was retrieved.

He cannot move the basket once it has been set up, nor can he set it up again once it has been retrieved.
Find the maximum number of apples that he can get.

Constraints

• $1 \leq N\leq 2\times 10^5$
• $1 \leq D\leq 2\times 10^5$
• $1 \leq W\leq 2\times 10^5$
• $1 \leq T_i\leq 2\times 10^5$
• $1 \leq X_i\leq 2\times 10^5$
• All pairs $(T_i,X_i)$ are different.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $D$ $W$
$T_1$ $X_1$
$T_2$ $X_2$
$\vdots$
$T_N$ $X_N$

Output

Print the maximum number of apples that Takahashi can get.

Sample Input 1

8 4 3
1 1
3 4
6 4
5 2
4 2
4 3
5 5
7 3

Sample Output 1

5

If Takahashi chooses $S=3$ and $L=2$, he will set up the basket to cover the range $1.5\leq x\leq 4.5$ from time $2.5$ to $6.5$. Then, he gets the following five apples:

• The apple that falls at coordinate $X_2=4$ at time $T_2=3$
• The apple that falls at coordinate $X_3=4$ at time $T_3=6$
• The apple that falls at coordinate $X_4=2$ at time $T_4=5$
• The apple that falls at coordinate $X_5=2$ at time $T_5=4$
• The apple that falls at coordinate $X_6=3$ at time $T_6=4$

There is no way to get six or more apples, so print $5$.

问题描述

在数轴上有一排苹果树，$N$个苹果从树上落下。

具体来说，对于每个$1\leq i\leq N$，在时间$T_i$时，一个苹果会落在坐标$X_i$处。

高桥有一个耐久度为$D$、长度为$W$的篮子，他可以执行以下操作 恰好一次。

选择正整数$S$和$L$。他在时间$S-0.5$时将篮子设置在范围$L-0.5\leq x\leq L+W-0.5$，并在时间$S+D-0.5$时收回篮子。 他将篮子设置后到收回期间落在篮子覆盖范围内的所有苹果都拿走。

一旦篮子被设置，他就不能移动它，也不能再次设置它。一旦篮子被收回，他也不能再次设置它。

找出他能拿到的最大苹果数。

约束

• $1 \leq N\leq 2\times 10^5$
• $1 \leq D\leq 2\times 10^5$
• $1 \leq W\leq 2\times 10^5$
• $1 \leq T_i\leq 2\times 10^5$
• $1 \leq X_i\leq 2\times 10^5$
• 所有对$(T_i,X_i)$都不同。
• 所有输入值都是整数。

输入

输入数据通过标准输入给出，格式如下：

$N$ $D$ $W$
$T_1$ $X_1$
$T_2$ $X_2$
$\vdots$
$T_N$ $X_N$

输出

打印高桥可以拿到的最大苹果数。

样例输入1

8 4 3
1 1
3 4
6 4
5 2
4 2
4 3
5 5
7 3

样例输出1

5

如果高桥选择$S=3$和$L=2$，他将在时间$2.5$到$6.5$将篮子设置在范围$1.5\leq x\leq 4.5$。然后，他将拿到以下五个苹果：

• 在时间$T_2=3$落在坐标$X_2=4$的苹果
• 在时间$T_3=6$落在坐标$X_3=4$的苹果
• 在时间$T_4=5$落在坐标$X_4=2$的苹果
• 在时间$T_5=4$落在坐标$X_5=2$的苹果
• 在时间$T_6=4$落在坐标$X_6=3$的苹果

没有方法可以拿到六个或更多的苹果，所以打印$5$。