누적 거리

KOI 나라는 수직선 위에 놓인 \(N\)개의 마을로 구성되어 있다. 이 중 \(i\) (\(1 \le i \le N\))번째 마을은 \(x_{i}\) 위치에 놓여 있으며 \(a_{i}\)명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다.

KOI 나라는 모든 국민이 참여하는 모임을 개최하려고 한다. 모든 사람들이 모임 장소에 도착하기 위해 이동해야 하는 거리의 합을 누적 거리라고 부르고, 모임 장소가 \(x\)일 때의 누적 거리를 \(f\)(\(x\))로 나타내자.

\(i\)번째 마을에 사는 사람이 \(x\) 위치에서 열리는 모임에 참가하기 위해서 이동해야 하는 거리는 |\(x_{i}\) − \(x\)|이다. \(i\)번째 마을에는 \(a_{i}\)명이 거주 중이므로 \(i\)번째 마을에 사는 사람들의 이동 거리의 합은 \(a_{i}|x_{i}\) − \(x\)|가 된다. 이 값을 모든 마을에 대해 합한 값이 모임 장소가 \(x\)일 때의 누적 거리가 될 것이다. 즉, \(f\)(\(x\)) = \(a_{1} \times |x_{1} - x| + a_{2} \times |x_{2} - x| + \cdots + a_{n} \times |x_{n} - x|\)이다.

예를 들어 마을의 위치가 \(x_{1}\) = 1, \(x_{2}\) = 3, \(x_{3}\) = 6이고, 각 마을에 거주하는 사람들의 수가 \(a_{1}\) = 2, \(a_{2}\) = 1, \(a_{3}\) = 3이라고 하면, 모임 장소가 \(x = 4\)일 때의 누적 거리는 \(f\)(4) = \(2 \times |1 - 4| + 1 \times |3 - 4| + 3 \times |6 - 4| = 13\) 이다.

KOI 나라는 모임이 개최될 장소의 후보를 \(Q\)개 준비해 두었다. 이 때 \(j\) (\(1 \le j \le Q\))번째 후보 장소의 위치는 \(q_{j}\)이다. 이 때 서로 다른 두 후보 장소의 위치가 같은 경우는 없으나 마을의 위치와 후보 장소의 위치가 같을 수 있다. 각각의 후보 장소에 대해 누적 거리를 계산하는 프로그램을 작성하라.

Hint.

|\(x\)|는 \(x\) < 0이면 −\(x\), \(x \ge 0\)이면 \(x\)인 절댓값 기호이다.

참고: \(|x|\)는 \(x < 0\)이면 \(-x\), \(x \ge 0\)이면 \(x\)인 절댓값 기호이다.

• \(1 \le N \le 200\,000\)
• 모든 \(i\) (\(1 \le i \le N\)) 에 대해, \(1 \le a_i \le 1\,000\)
• 모든 \(i\) (\(1 \le i \le N\)) 에 대해, \(-10^{9} \le x_i \le 10^{9}\)
• \(1 \le Q \le 200\,000\)
• 모든 \(j\) (\(1 \le j \le Q\)) 에 대해, \(-10^{9} \le q_j \le 10^{9}\)
• \(1 \le i_1 < i_2 \le N\) 에 대해 \(x_{i_1} \ne x_{i_2}\). 즉, 모든 마을의 위치는 서로 다르다.
• \(1 \le j_1 < j_2 \le Q\) 에 대해 \(q_{j_1} \ne q_{j_2}\). 즉, 모든 후보 장소의 위치는 서로 다르다.
• 주어지는 모든 수는 정수이다.

첫 번째 줄에 \(N\)과 \(Q\)가 공백을 사이에 두고 차례로 주어진다.

다음 \(N\)개의 줄에는 마을에 대한 정보가 주어진다. 이 중 \(i\) (\(1 \le i \le N\))번째 줄에는 \(a_{i}\)와 \(x_{i}\)가 공백을 사이에 두고 차례로 주어진다.

다음 \(Q\)개의 줄에는 모임 장소 후보에 대한 정보가 주어진다. 이 중 \(j\) (\(1 \le j \le Q\))번째 줄에는 \(q_{j}\)가 주어진다.

\(j\) (\(1 \le j \le Q\))번째 줄에 모임 장소가 \(j\)번째 후보 모임 장소인 \(q_{j}\)일 때의 누적 거리, 즉 \(f\)(\(q_{j}\))의 값을 출력한다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2021 > 2차 대회 > 중등부 2번