#2419. 人工湖

人工湖

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

夏日那让人喘不过气的酷热将奶牛们的烦躁情绪推到了最高点.最终,约翰决定建一个人工湖供奶牛消暑之用.

为了使湖看起来更加真实,约翰决定将湖的横截面建成N(1\red{N(1≤}N\red{N≤}105)\red{105)}个连续的平台高低错落的组合状,所有的平台从左到右按1\red{1}N\red{N}依次编号.当然咯,在湖中注入水后,这些平台都将被淹没.

平台i\red{i}在设计图上用它的宽度wi(l\red{wi(l≤}wi\red{wi≤}1000)\red{1000)}和高度(你可以理解为该平台顶离约翰挖的地基的高度)Hi.\red{Hi.(}1\red{1≤}Hi\red{Hi ≤}1000000\red{1000000)}来描述的.所有平台的高度都是独一无二的.湖的边缘可以视为无限高的平台.下面给出了一张约翰的设计图: img

按约翰的设想,在坑挖好后,他会以1\red{1}单位每分钟的速度往最低的那个平台上注水.水在离开水管后立即下落,直到撞到平台顶或是更早些时候注入的水然后,与所有常 温下的水一样,它会迅速地流动、扩散.

简单起见,你可以认为这些都是在瞬间完成的.约翰想知道,对于每一个平台,它的顶部是从哪个时刻开始,与水面的距离至少为1\red{1}单位长度.

注意:数据不保证答案全部在32\red{32}位整型变量的范围内

输入格式

1\red{1}行: 1\red{1}个整数,N\red{N}

2..N+1\red{2..N+1}行: 第i+1\red{i+1}行为2\red{2}个用空格隔开的整数Wi\red{W_i}Hi\red{H_i,}描述了第i\red{i}个平台

输出格式

1..N\red{1..N}行:

i\red{i}行为1\red{1}个整数,表示平台i\red{i}的顶到水面的距离从何时开始大于1\red{1 }单位长度

样例

输入样例

3
4 2
2 7
6 4

输出样例

4
50
26

提示

输入对应了题目中给出的例子,一共有3\red{3}个平台,约翰选定的注水点在最低的1\red{1}号平台上方.

4\red{4}分钟后乎台1\red{1}被淹没.

26\red{26}分钟后平台3\red{3}被淹没.

50\red{50}分钟后平台2\red{2}被淹没.

输入说明:

输入对应了题目中给出的例子,一共有3\red{3}个平台,FJ\red{FJ}选定的注水点在最低的1\red{1}号平台上方。

数据结构

未参加
状态
已结束
规则
IOI
题目
14
开始于
2023-1-7 14:00
结束于
2023-1-8 14:00
持续时间
24 小时
主持人
参赛人数
18