KOI 2차 2021 중2- 누적 거리 > 문제은행 : 정보올림피아드&알고리즘


4803 : 누적 거리

제한시간
3000 ms   
메모리제한
1024 MB   
해결횟수
23 회   
시도횟수
41 회   

문제

누적 거리

KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다. 

이 중 i (1 ≤ i ≤ N)번째 마을은 xi 위치에
놓여 있으며 ai명이 거주 중이다. 

또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다.

 

KOI 나라는 모든 국민이 참여하는 모임을 개최하려고 한다. 

모든 사람들이 모임 장소에 도착하기 위해
이동해야 하는 거리의 합을 누적 거리라고 부르고, 

모임 장소가 x일 때의 누적 거리를 f(x)로 나타내자. 

 

i번째 마을에 사는 사람이 x 위치에서 열리는 모임에 참가하기 위해서 이동해야 하는 거리는 |xi − x|이다. 

i번째 마을에는 ai명이 거주 중이므로 i번째 마을에 사는 사람들의 이동 거리의 합은 ai|xi − x|가 된다. 

이 값을 모든 마을에 대해 합한 값이 모임 장소가 x일 때의 누적 거리가 될 것이다. 

즉, f(x) = a1 × |x1 − x| + a2 × |x2 − x| + · · · + an × |xn − x| = ∑N​i=1 ai × |xi − x|이다. 

 

예를 들어 마을의 위치가 x1 = 1, x2 = 3, x3 = 6이고, 

각 마을에 거주하는 사람들의 수가 a1 = 2, a2 = 1, a3 = 3이라고 하면, 

모임 장소가 x = 4일 때의 누적 거리는 f(4) = 2×|1−4|+ 1×|3−4|+ 3×|6−4| = 13 이다. 

 

KOI 나라는 모임이 개최될 장소의 후보를 Q개 준비해 두었다. 

이 때 j (1 ≤ j ≤ Q)번째 후보 장소의 위치는 qj이다. 

이 때 서로 다른 두 후보 장소의 위치가 같은 경우는 없으나 마을의 위치와 후보 장소의 위치가 같을 수 있다. 

각각의 후보 장소에 대해 누적 거리를 계산하는 프로그램을 작성하라. 

 

참고 

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

 


제약 조건 

• 1 ≤ N ≤ 200 000 

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

• 모든 i (1 ≤ i ≤ N)에 대해, −109 ≤ xi ≤ 109 

• 1 ≤ Q ≤ 200 000 

• 모든 j (1 ≤ j ≤ Q)에 대해, −109 ≤ qj ≤ 109 

• 1 ≤ i1 < i2 ≤ N에 대해 xi1 ≠ xi2
. 즉, 모든 마을의 위치는 서로 다르다. 

• 1 ≤ j1 < j2 ≤ Q에 대해 qj1
qj2
. 즉, 모든 후보 장소의 위치는 서로 다르다. 

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

 

부분문제 

1. (9점) N, Q ≤ 5 000 

2. (21점) 

• 모든 i (1 ≤ i ≤ N)에 대해 1 ≤ xi ≤ 200 000 

• 모든 j (1 ≤ j ≤ Q)에 대해 1 ≤ qj ≤ 200 000 

3. (25점) 모든 i (1 ≤ i ≤ N)에 대해 ai = 1 

4. (45점) 추가 제약 조건 없음. 

 


입력형식

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

 

  다음 N개의 줄에는 마을에 대한 정보가 주어진다. 

이 중 i (1 ≤ i ≤ N)번째 줄에는 ai와 xi가 공백을 사이에 두고 차례로 주어진다. 

 

  다음 Q개의 줄에는 모임 장소 후보에 대한 정보가 주어진다. 

이 중 j (1 ≤ j ≤ Q)번째 줄에는 qj가 주어진다. 


출력형식

  j (1 ≤ j ≤ Q)번째 줄에 모임 장소가 j번째 후보 모임 장소인 qj일 때의 누적 거리, 

즉 f(qj )의 값을 출력한다.  


입력 예

3 1
2 1
1 3
3 6
4

출력 예

13

입력 예

4 5
3 -4
1 -10
2 11
4 6
6
-5
1
-12
14

출력 예

56
84
66
144
116


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP