分数: 333 分
问题陈述
高桥和青木分别搬家并开始在新城镇生活。他们想要找到距离他们居住地最近的邮局并注册其服务。
这个城镇可以表示为一条只有一条道路的数轴,并且有 N 邮局分布在道路两旁。的 i-第邮局位于坐标 X_i 目前有 C_i 注册用户。请注意,邮局不一定按坐标排序。
高桥住在坐标 P,青木住在坐标 Q。他们每个人都在离他们居住地最近的邮局独立登记。在这里,一个人的住所和邮局之间的距离是用它们的坐标的绝对差来测量的。如果有多个最近的邮局,他们会选择坐标最小的一个。
由于每个人的注册,他们选择的邮局的注册用户数量增加了 1。如果两者在同一个邮局注册,则该邮局的注册用户数增加 2.
两个注册完成后,让 S 是 Takahashi 和 Aoki 注册的邮局集合(如果两者在同一邮局注册, S 只包含该邮局一次)。对于每个邮局 S,注册完成后判断注册用户数,并输出总数。
约束
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq P \leq 10^9
- -10^9 \leq Q \leq 10^9
- -10^9 \leq X_i \leq 10^9
- 0 \leq C_i \leq 10^9
- X_i \neq X_j (i \neq j)
- 所有输入均为整数
输入
N P Q X_1 C_1 X_2 C_2 \vdots X_N C_N
- 第一行包含 N,邮局数量, P,高桥居住的坐标,以及 Q,青木所在的坐标,以空格分隔。
- 从第 2 行到 (N + 1)第行,给出了每个邮局的信息。
- 的 (1 + i)第行包含坐标 X_i 以及当前注册用户数 C_i 的 i第一个邮局,以空格分隔。
输出
一行输出各邮局注册完成后的注册用户总数 S.
示例输入 1
3 5 15 0 10 10 20 20 30
示例输出 1
32
示例输入 2
4 0 0 -5 100 5 200 3 50 -3 80
示例输出 2
82
示例输入 3
5 -1000000000 1000000000 0 500000000 -999999999 100 1000000000 300000000 -500000000 200000000 500000000 150000000
示例输出 3
300000102