時間限制 2000 ms ・ 記憶體限制 512 MB
題目描述
一根棍子原本覆蓋數線 [0,L]。要依指定順序切 n 刀，每刀在給定座標把當時包含該位置的一段棍子分成兩段；此刀成本等於該段切割前的長度。求 n 刀的總成本，切割順序不可改變。
輸入格式
第一行為 n、L，1 ≤ n ≤ 200000，1 ≤ L ≤ 10^7。接著 n 行各為 x、i，表示第 i 刀的切割座標是 x。所有 i 恰為 1 至 n 的排列；輸入各行不保證按切割順序排列，x 為原棍子上的有效切割位置。
輸出格式
輸出總成本。答案可能超過 2^31，但不超過 2^60。
範例測資
範例輸入 1
3 7 2 2 3 1 5 3
範例輸出 1
14
請先登入後再提交程式碼
討論與題解
載入討論區…