/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1,2,\ldots ,N の番号のついた N 人の人を数直線上に並べます。人 i\,(1 \leq i \leq N) がいる地点の座標を x_i としたとき、 x_i は L_i 以上 R_i 以下の整数である必要があります。複数の人が同じ座標にいても構いません。
ここで、並べ方の不満度を以下の式で定義します。
\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}|x_j-x_i|
不満度としてあり得る値の最小値を求めてください。
制約
- 2 \leq N \leq 3 \times 10^5
- 1 \leq L_i \leq R_i \leq 10^7 \,(1 \leq i \leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
答えを出力せよ。
入力例 1
3 1 3 2 4 5 6
出力例 1
4
x_1=3,x_2=4,x_3=5 とすると、不満度は 4 です。不満度を 3 以下にすることはできないので、4 を出力します。
入力例 2
3 1 1 1 1 1 1
出力例 2
0
入力例 3
6 1 5 2 4 1 1 4 4 3 6 3 3
出力例 3
15
Score : 600 points
Problem Statement
N people, numbered 1,2,\ldots ,N, are going to stand on the number line. Let's denote by x_i the coordinate the Person i stands at. Then, x_i should be an integer satisfying L_i \leq x_i \leq R_i. Multiple people can occupy the same coordinate.
We define the dissatisfaction level as the following formula:
\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}|x_j-x_i|
Find the minimum possible value of the dissatisfaction level.
Constraints
- 2 \leq N \leq 3 \times 10^5
- 1 \leq L_i \leq R_i \leq 10^7 \,(1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L_1 R_1 L_2 R_2 \vdots L_N R_N
Output
Print the answer.
Sample Input 1
3 1 3 2 4 5 6
Sample Output 1
4
If we let x_1=3,x_2=4,x_3=5, we get the dissatisfaction level of 4. We cannot make it 3 or less, so the answer is 4.
Sample Input 2
3 1 1 1 1 1 1
Sample Output 2
0
Sample Input 3
6 1 5 2 4 1 1 4 4 3 6 3 3
Sample Output 3
15