有一根長(zhǎng)度為 len 的橫向的管道,該管道按照單位長(zhǎng)度分為 len 段,每一段的中央有一個(gè)可開(kāi)關(guān)的閥門和一個(gè)檢測(cè)水流的傳感器。
一開(kāi)始管道是空的,位于 Li 的閥門會(huì)在 Si 時(shí)刻打開(kāi),并不斷讓水流入管道。
對(duì)于位于 Li 的閥門,它流入的水在 Ti (Ti ≥ Si) 時(shí)刻會(huì)使得從第 Li?(Ti?Si) 段到第 Li + (Ti ? Si) 段的傳感器檢測(cè)到水流。 求管道中每一段中間的傳感器都檢測(cè)到有水流的最早時(shí)間。
輸入的第一行包含兩個(gè)整數(shù) n, len,用一個(gè)空格分隔,分別表示會(huì)打開(kāi)的閥門數(shù)和管道長(zhǎng)度。
接下來(lái) n 行每行包含兩個(gè)整數(shù) Li , Si,用一個(gè)空格分隔,表示位于第 Li 段 管道中央的閥門會(huì)在 Si 時(shí)刻打開(kāi)。
3 10 1 1 6 5 10 2
5
對(duì)于 30% 的評(píng)測(cè)用例,n ≤ 200,Si,len ≤ 3000 ;
對(duì)于 70% 的評(píng)測(cè)用例,n ≤ 5000,Si,len ≤ 105 ;
對(duì)于所有評(píng)測(cè)用例,1 ≤ n ≤ 105,1 ≤ Si , len ≤ 109,1 ≤ Li ≤ len,Li?1 < Li
1. 對(duì)于編程題目,不能使用諸如繪圖、硬件操作或與操作系統(tǒng)相關(guān)的 API。
2. 所有依賴的模塊(如 math)必須明確地在源文件中 import。
3. 只能使用 python 自帶的模塊,使用 pip 等安裝的擴(kuò)展模塊無(wú)法使用。
4. 提交時(shí),注意選擇使用Python語(yǔ)言。
比賽結(jié)束依舊可以訓(xùn)練,請(qǐng)見(jiàn)題集2022年第十三屆藍(lán)橋杯大賽軟件類省賽Python大學(xué)B組真題