Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register
Language:
Artificial Lake
 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 2326 Accepted: 785

Description

The oppressively hot summer days have raised the cows' clamoring to its highest level. Farmer John has finally decided to build an artificial lake. For his engineering studies, he is modeling the lake as a two-dimensional landscape consisting of a contiguous sequence of N soon-to-be-submerged levels (1 ≤ N ≤ 100,000) conveniently numbered 1..N from left to right.

Each level i is described by two integers, its width Wi (1 ≤ Wi ≤ 1,000) and height (like a relative elevation) Hi (1 ≤ Hi ≤ 1,000,000). The heights of FJ's levels are unique. An infinitely tall barrier encloses the lake's model on the left and right. One example lake profile is shown below.

```
*             *  :
*             *  :
*             *  8
*    ***      *  7
*    ***      *  6
*    ***      *  5
*    **********  4 <- height
*    **********  3
***************  2
***************  1
Level    |  1 |2|  3   |```

In FJ's model, he starts filling his lake at sunrise by flowing water into the bottom of the lowest elevation at a rate of 1 square unit of water per minute. The water falls directly downward until it hits something, and then it flows and spreads as room-temperature water always does. As in all good models, assume that falling and flowing happen instantly. Determine the time at which each elevation's becomes submerged by a single unit of water.

```WATER              WATER OVERFLOWS
|                       |
* |          *      *     |      *      *            *
* V          *      *     V      *      *            *
*            *      *    ....    *      *~~~~~~~~~~~~*
*    **      *      *~~~~** :    *      *~~~~**~~~~~~*
*    **      *      *~~~~** :    *      *~~~~**~~~~~~*
*    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*
*    *********      *~~~~*********      *~~~~*********
*~~~~*********      *~~~~*********      *~~~~*********
**************      **************      **************
**************      **************      **************

After 4 mins        After 26 mins       After 50 mins
Lvl 1 submerged     Lvl 3 submerged     Lvl 2 submerged```

Warning: The answer will not always fit in 32 bits.

Input

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 describes level i with two space-separated integers: Wi and Hi

Output

* Lines 1..N: Line i contains a single integer that is the number of minutes that since sunrise when level #i is covered by water of height 1.

Sample Input

```3
4 2
2 7
6 4
```

Sample Output

```4
50
26

```

Source

[Submit]   [Go Back]   [Status]   [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator