페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4803
서브태스크

누적 거리 3s 1024MB

문제

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

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

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

예를 들어 마을의 위치가 x_1 = 1, x_2 = 3, x_3 = 6이고, 각 마을에 거주하는 사람들의 수가 a_1 = 2, a_2= 1, a_3 = 3이라고 하면, 모임 장소가 x = 4일 때의 누적 거리는 f(4) = 2×|1−4|+ 1×|3−4|+ 3×|6−4| = 13 이다. 

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

참고

|x|는 x < 0이면 −x, x ≥ 0이면 x인 절댓값 기호이다.


입력

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

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

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

제약 조건

  • 1 ≤ N ≤ 200\,000 

  • 모든 i (1 ≤ i ≤ N)에 대해, 1 ≤ a_i ≤ 1\,000

  • 모든 i (1 ≤ i ≤ N)에 대해, −10^9 ≤ x_i ≤ 10^9

  • 1 ≤ Q ≤ 200\,000 

  • 모든 j (1 ≤ j ≤ Q)에 대해, −10^9 ≤ q_j ≤ 10^9

  • 1 ≤ i_1 < i_2 ≤ N에 대해 x_{i_1}≠x_{i_2}. 즉, 모든 마을의 위치는 서로 다르다. 

  • 1 ≤ j_1 < j_2 ≤ Q에 대해 q_{j_1} ≠​ q_{j_2}. 즉, 모든 후보 장소의 위치는 서로 다르다. 

  • 주어지는 모든 수는 정수이다. 


출력

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


부분문제

번호 점수 조건
#19점

N, Q ≤ 5\,000 

#221점

모든 i (1 ≤ i ≤ N)에 대해 1 ≤ x_i ≤ 200\,000 

모든 j (1 ≤ j ≤ Q)에 대해 1 ≤ q_j ≤ 200\,000 

#325점

모든 i (1 ≤ i ≤ N)에 대해 a_i = 1

#445점

추가 제약 조건 없음.


예제 #1

3 1

2 1

1 3

3 6

4
13

예제 #2

4 5

3 -4

1 -10

2 11

4 6

6

-5

1

-12

14
56

84

66

144

116


출처

KOI 2차 2021 중등 2
로그인해야 코드를 작성할 수 있어요.