Problem : 315 - 城市規劃

Problem Statistics

Solved Member: 29　　Submission: 131　　User Tried: 34

Statement:

segment city 是一條線構成的城市，整個城市是一個一維座標系。

這個城市最近做了都市規劃，依序規劃了 n 個特區，每個特區是一個連續的區間 [l,r] (l≤r)，並且可能會有多個特區重疊。

這個城市希望能建造一個市政府（視做一個點），並且希望市政府到所有特區的距離和越小越好。現在要依序給你 n 個區域的位置，問你每建完一個新的特區以後，市政府到所有特區的總和最小能有多小。

/*
我們說一個點 x 到特區 [l,r] 的距離代表 x 離 [l,r] 中最近的地方距離。
例如點 3 到 [7,9] 距離 4，（到 7 的距離）
而點 2 到 [1,3] 距離 0。
*/

Input:Output:

第一行有一個數字 n ，代表這個城市規劃了 n 個特區。
接下來 n 行，每一行有兩個數字 l,r ，代表新建了一個特區在 [l,r] 之間。

40% 測試資料滿足：n ≤ 2000
n ≤ 2000000
0 ≤ l ≤ r ≤ 2000000000

請輸出 n 行，每行一個數字。
第 i 行代表當前 i 個特區建完了以後，市政府離所有特區最短的距離和。

Sample Input:Sample Output:

5
1 4
5 8
2 6
3 7
4 9

0
1
1
1
1

HINT:

範例測資中，每次蓋完後將市政府蓋在 4 都會是最佳選擇。

Source:

TOI 2013 1模

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1-1	1000ms	262144kb	20
1-2	1000ms	262144kb
2-1	1000ms	262144kb	20
2-2	1000ms	262144kb
3-1	1000ms	262144kb	20
3-2	1000ms	262144kb
4-1	1000ms	262144kb	20
4-2	1000ms	262144kb
5-1	20000ms	262144kb	20
5-2	20000ms	262144kb
5-3	20000ms	262144kb