BAEKJOON 22345번: 누적거리

https://www.acmicpc.net/problem/22345

22345번: 누적 거리

이전에 포스팅한 Stadium이라는 문제와 매우 유사하다.

다만 이 문제에서는 x좌표가 정렬이 되어있지 않으므로 정렬을 해주어야 한다.

그리고 주어지는 후보지점에서의 값을 계산해주면 된다.

 

Stadium에서는 변화량에 집중하였다면 이번에는 그냥 계산하면 된다.

누적 거리를 구하기 위해서는 각 쿼리가 어떠한 두 마을 사이에 있는지 알아야 하며, 이를 이분탐색을 통해 찾아준다.

 

각 쿼리에 대한 누적 거리의 계산을 상수시간에 처리하기 위해 전처리를 조금 해주어야 한다.

 

x좌표를 기준으로 정렬한 후, 각 마을마다 a_i와 x_i를 곱한 값을 누적하여 더해준다. 이는 왼쪽에서부터, 오른쪽에서부터 따로 저장하여 둔다.

 

이제 계산만 하면 된다. 나머지는 아래 코드를 참고하기 바란다.

 

#include<bits/stdc++.h>
#define F(N) for(int i=1;i<=N;i++)
using namespace std;
const int r=2e5+3;
struct w{long long x,a;}A[r];
inline bool c(w d,w f){return d.x<f.x;}
long long L[r],R[r],S[r],X[r],N,Q,q,p,t;
int main(){
    scanf("%lld%lld",&N,&Q);
    F(N)scanf("%lld%lld",&A[i].a,&A[i].x);
    sort(A+1,A+1+N,c);
    F(N){X[i]=A[i].x;t=N-i+1;S[i]=S[i-1]+A[i].a;L[i]=L[i-1]+A[i].a*A[i].x;R[t]=R[t+1]+A[t].a*A[t].x;}
    F(Q){
        scanf("%lld",&q);
        p=lower_bound(X+1,X+N+1,q)-X;
        printf("%lld\n",q*S[p-1]-L[p-1]+R[p]-q*(S[N]-S[p-1]));
    }
    return 0;
}