1000 . 牛肉麵店的隊伍

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

pring

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

ntucpc-speedrun2

Description

完整題本 PDF：中文、英文、馬來文。

臺灣一向以種種美食聞名。不過，就算有那麼多美食，臺灣人還是很喜歡排在長長的隊伍中等著吃飯。

在這家有名的牛肉麵店，廚房一次只能煮一位客人的餐點。第 $i$ 個客人在 $t_i$ 時刻到達，而他點的餐點需要花 $w_i$ 分鐘來煮。當客人到達時，如果廚房沒有正在處理其他客人的餐點，那就會立刻開始煮他的。否則，他將會排到隊伍的最後面。每個人都會好好遵守規則，不會插隊。廚房在前一個餐點煮完的瞬間，馬上就可以開始煮下一個客人的餐點。現在，請計算每位客人各需要等多久才能等到他們的餐點。

Input Format

第一行有一個正整數 $N$。

接下來的 $N$ 行，每行有兩個正整數 $t_i, w_i$。

  • $1 \leq N \leq 10 ^ 5$
  • $1 \leq t_i, w_i \leq 10 ^ 9$
  • $t$ 是嚴格遞增的，換句話說 $\forall 1\leq i <N, t_i < t_{i+1}$。

Output Format

輸出 $N$ 行，每行一個正整數。第 $i$ 行表示第 $i$ 個客人等了多久才拿到他們的餐點。

Sample Input 1

3
1 5
2 1
7 5

Sample Output 1

5
5
5

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 2097152 65536
1 1000 2097152 65536
2 1000 2097152 65536
3 1000 2097152 65536
4 1000 2097152 65536
5 1000 2097152 65536
6 1000 2097152 65536
7 1000 2097152 65536
8 1000 2097152 65536
9 1000 2097152 65536
10 1000 2097152 65536
11 1000 2097152 65536
Submit
Back to Top