← 返回题目列表

AtCoder · awc0055_b

B. 最近的邮局

中文机器翻译题面 查看原题

分数: 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