백준 22345 누적거리

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

22345번: 누적 거리

 

마을이 총 20만개 이며 거리질의 또한 20만이므로 O(N^2)시간복잡도로 풀수 없습니다.

즉, 한 마을에 대해서 모든 마을의 거리를 계산하면 시간초과가 납니다. 

따라서 우리가 배열에 흔히 쓰는 prefix sum을 마을에 대한 누적 거리 합을 저장하면 됩니다.

저는 마을 사람수를 정렬한 후 참조하려고 map을 썼지만 풀고 나니 map을 안썼어도 좋았겠네요.

거리 질의가 주어질때 좌표에 대해 이진탐색을 한 후 양옆 누적합을 참조하여 답을 구하면 됩니다.

O(NlogN)으로 풀 수 있습니다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
vector<int> vec;
map<int,int> m;
map<int,long long> l;
map<int,long long> r;
map<int,long long> kl;
map<int,long long> kr;
int main(){
    int N,Q;
    scanf("%i%i",&N,&Q);
    for(int x=0;x<N;x++){
        int a,b;
        scanf("%i%i",&a,&b);
        vec.push_back(b);
        m[b]=a;
    }
    sort(vec.begin(),vec.end());
    long long temp=0;
    long long k=0;
    for(int x=0;x<N;x++){
        if(x==0){
            l[vec[0]]=0;
            k+=m[vec[0]];
            kl[vec[0]]=k;
            continue;
        }
        temp+=(long long)(vec[x]-vec[x-1])*k;
        l[vec[x]]=temp;
        k+=m[vec[x]];
        kl[vec[x]]=k;
    }
    k=0;
    temp=0;
    for(int x=N-1;x>=0;x--){
        if(x!=N-1){
            temp+=(long long)(vec[x+1]-vec[x])*k;
        }
        r[vec[x]]=temp;
        k+=m[vec[x]];
        kr[vec[x]]=k;
    }
    for(int x=0;x<Q;x++){
        int input;
        scanf("%i",&input);
        int rv=upper_bound(vec.begin(),vec.end(),input)-vec.begin();
        if(rv==0){
            printf("%lli\n",r[vec[rv]]+kr[vec[rv]]*(long long)abs(input-vec[0]));
        }
        else if(rv==N){
            printf("%lli\n",l[vec[rv-1]]+kl[vec[rv-1]]*(long long)abs(input-vec[N-1]));
        }
        else{
            printf("%lli\n",l[vec[rv-1]]+r[vec[rv]]+kl[vec[rv-1]]*(long long)abs(input-vec[rv-1])+kr[vec[rv]]*(long long)abs(input-vec[rv]));
        }
    }
}