/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君と青木君は、それぞれ引っ越しを終えて新しい街に住み始めました。二人は自分の住んでいる場所から最寄りの郵便局を見つけて、利用登録をしたいと考えています。
この街は 1 本の道路を数直線で表すことができ、道路上には N 個の郵便局が点在しています。i 番目の郵便局は座標 X_i の位置にあり、現在 C_i 人の利用者が登録されています。なお、郵便局は座標の昇順に並んでいるとは限りません。
高橋君は座標 P に、青木君は座標 Q に住んでいます。二人はそれぞれ独立に、自分の住んでいる場所から最も近い郵便局に利用登録を行います。ここで、自分の住んでいる場所と郵便局との距離は、座標の差の絶対値で測ります。最も近い郵便局が複数ある場合は、その中で座標が最も小さいものを選びます。
二人がそれぞれ登録を行った結果、登録先の郵便局の利用登録者数はそれぞれ 1 増えます。二人が同じ郵便局に登録した場合、その郵便局の利用登録者数は 2 増えます。
二人の登録がすべて完了した後、高橋君が登録した郵便局と青木君が登録した郵便局からなる集合を S とします（二人が同じ郵便局に登録した場合、S にはその郵便局が 1 つだけ含まれます）。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
- 1 行目には、郵便局の数を表す N 、高橋君の住んでいる座標を表す P 、青木君の住んでいる座標を表す Q が、スペース区切りで与えられる。
- 2 行目から N + 1 行目では、各郵便局の情報が与えられる。
- 1 + i 行目では、 i 番目の郵便局の座標 X_i と現在の利用登録者数 C_i が、スペース区切りで与えられる。
出力
S に含まれる各郵便局の登録完了後の利用登録者数の合計を、1 行に出力してください。
入力例 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
Score : 333 pts
Problem Statement
Takahashi and Aoki have each finished moving and started living in a new town. They want to find the nearest post office from where they live and register for its services.
This town can be represented as a number line with a single road, and there are N post offices scattered along the road. The i-th post office is located at coordinate X_i and currently has C_i registered users. Note that the post offices are not necessarily ordered by coordinate.
Takahashi lives at coordinate P, and Aoki lives at coordinate Q. Each of them independently registers at the post office closest to where they live. Here, the distance between a person's residence and a post office is measured as the absolute difference of their coordinates. If there are multiple closest post offices, they choose the one with the smallest coordinate.
As a result of each person's registration, the number of registered users at their chosen post office increases by 1. If both register at the same post office, the number of registered users at that post office increases by 2.
After both registrations are complete, let S be the set of post offices where Takahashi and Aoki registered (if both registered at the same post office, S contains that post office only once). For each post office in S, determine the number of registered users after registration is complete, and output the total.
Constraints
- 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)
- All inputs are integers
Input
N P Q X_1 C_1 X_2 C_2 \vdots X_N C_N
- The first line contains N, the number of post offices, P, the coordinate where Takahashi lives, and Q, the coordinate where Aoki lives, separated by spaces.
- From the 2nd line to the (N + 1)-th line, information about each post office is given.
- The (1 + i)-th line contains the coordinate X_i and the current number of registered users C_i of the i-th post office, separated by spaces.
Output
Output in one line the total number of registered users after registration is complete for each post office in S.
Sample Input 1
3 5 15 0 10 10 20 20 30
Sample Output 1
32
Sample Input 2
4 0 0 -5 100 5 200 3 50 -3 80
Sample Output 2
82
Sample Input 3
5 -1000000000 1000000000 0 500000000 -999999999 100 1000000000 300000000 -500000000 200000000 500000000 150000000
Sample Output 3
300000102