f607: 3. 切割費用
Tags : APCS
Accepted rate : 290人/388人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-01-09 17:55

Content

有一根長度為 $L$ 的棍子,你會把這個棍子切割 $n$ 次。

假設一開始棍子左端放在數線上 $0$ 的位置,棍子的右端放在數線上 $L$ 的位置,每次的切割會給定一個介於 $0$ 到 $L$ 的數字表示要切個的位置,你要把穿過個這位置的棍子切成兩段,而所需的花費就等於所切割的棍子的長度。

Input

第一行有兩個整數 $n, L$。

接下來 $n$ 行每行有兩個整數 $x, i$,表示 $x$ 位置被切過一刀,而這刀是全部的切割中的第 $i$ 刀,保證 $i$ 是介於 $[1,n]$ 的整數且不會重複。

配分

  • 20分: $1\leq n \leq 1000, 1\leq L \leq 10^7$
  • 30分: $1\leq n \leq 50000, 1\leq L \leq 10^7$
  • 50分: $1\leq n \leq 200000, 1\leq L \leq 10^7$
Output

輸出一個整數表示總共的切割費用,答案可能超過 $2^{31}$ 但不會超過 $2^{60}$。

Sample Input #1
3 7
2 2
3 1
5 3
Sample Output #1
14
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 2.0s , <1M
公開 測資點#1 (5%): 2.0s , <1M
公開 測資點#2 (5%): 2.0s , <1M
公開 測資點#3 (5%): 2.0s , <1M
公開 測資點#4 (5%): 2.0s , <1M
公開 測資點#5 (5%): 2.0s , <1M
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <1M
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <10M
公開 測資點#11 (5%): 2.0s , <10M
公開 測資點#12 (5%): 2.0s , <10M
公開 測資點#13 (5%): 2.0s , <10M
公開 測資點#14 (5%): 2.0s , <10M
公開 測資點#15 (5%): 2.0s , <10M
公開 測資點#16 (5%): 2.0s , <10M
公開 測資點#17 (5%): 2.0s , <10M
公開 測資點#18 (5%): 2.0s , <10M
公開 測資點#19 (5%): 2.0s , <10M
Hint :
Tags:
APCS
出處:
2021年1月APCS [管理者:
cthbst (吳宗達)
]


ID User Problem Subject Hit Post Date
24742 f607
206 2021-03-19 21:49
24615
Hsu0905 (怎麼又是WA)
f607
187 2021-03-11 09:19
24567
wallacechu04... (Wallace Chu)
f607
lower_bound c++
233 2021-03-05 21:26
24082
asnewchien@g... (david)
f607
python 心得
550 2021-01-16 18:12
24042
cthbst (吳宗達)
f607
本題測試資料
554 2021-01-11 11:48