아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

간단한 문제

시간 제한4초메모리 제한1024 MB

요약
길이 N인 두 수열 p와 q가 주어질 때, 모든 순서쌍에 대해 p 거리와 q 거리 중 작은 값의 합을 구한다. N은 최대 100만이다.
난이도

어려움10점 중 8점

유형
정렬, 분할 정복, 세그먼트 트리, 수학
정답자
아직 제출이 없습니다

문제

길이가 NN인 두 수열 (p1,p2,…,pN)(p_1, p_2, \ldots, p_N), (q1,q2,…,qN)(q_1, q_2, \dots, q_N) 이 주어진다.

이때 다음 값을 구하여라.

∑i=1N∑j=1Nmin⁡(∣pi−pj∣,∣qi−qj∣)\sum_{i=1}^{N} {\sum_{j=1}^{N} {\min(|p_i - p_j|, |q_i - q_j|)} }

입력

첫째 줄에 수열의 길이 NN(1≤N≤1 000 000 1 \leq N \leq 1\ 000\ 000) 이 주어진다.

둘째 줄에는 정수 p1,p2,…,pNp_1, p_2, \ldots, p_N 이 공백으로 구분되어 주어진다. (1≤pi≤1 000 0001 \leq p_i \leq 1\ 000\ 000)

셋째 줄에는 정수 q1,q2,…,qNq_1, q_2, \ldots, q_N 이 공백으로 구분되어 주어진다. (1≤qi≤1 000 0001 \leq q_i \leq 1\ 000\ 000)

출력

첫째 줄에 문제의 답을 출력한다.

예제2

  1. 예제 1

    입력
    3
    1 3 2
    1 2 3
    
    예상 출력
    6
    
  2. 예제 2

    입력
    4
    1 1 1000000 1000000
    1000000 1000000 1 1
    
    예상 출력
    7999992