B. Producing Snow

Codeforces

IDCF947B

Time1000ms

Memory256MB

Difficulty—

binary searchdata structuresimplementation

Alice likes snow a lot! Unfortunately, this year's winter is already over, and she can't expect to have any more of it. Bob has thus bought her a gift — a large snow maker. He plans to make some amount of snow every day. On day _i_ he will make a pile of snow of volume _V__i_ and put it in her garden. Each day, every pile will shrink a little due to melting. More precisely, when the temperature on a given day is _T__i_, each pile will reduce its volume by _T__i_. If this would reduce the volume of a pile to or below zero, it disappears forever. All snow piles are independent of each other. Note that the pile made on day _i_ already loses part of its volume on the same day. In an extreme case, this may mean that there are no piles left at the end of a particular day. You are given the initial pile sizes and the temperature on each day. Determine the total volume of snow melted on each day. ## Input The first line contains a single integer _N_ (1 ≤ _N_ ≤ 105) — the number of days. The second line contains _N_ integers _V_1, _V_2, ..., _V__N_ (0 ≤ _V__i_ ≤ 109), where _V__i_ is the initial size of a snow pile made on the day _i_. The third line contains _N_ integers _T_1, _T_2, ..., _T__N_ (0 ≤ _T__i_ ≤ 109), where _T__i_ is the temperature on the day _i_. ## Output Output a single line with _N_ integers, where the _i_\-th integer represents the total volume of snow melted on day _i_. [samples] ## Note In the first sample, Bob first makes a snow pile of volume 10, which melts to the size of 5 on the same day. On the second day, he makes another pile of size 10. Since it is a bit warmer than the day before, the first pile disappears completely while the second pile shrinks to 3. At the end of the second day, he has only a single pile of size 3. On the third day he makes a smaller pile than usual, but as the temperature dropped too, both piles survive till the end of the day.

Samples

Input #1

3
10 10 5
5 7 2

Output #1

5 12 4

Input #2

5
30 25 20 15 10
9 10 12 4 13

Output #2

9 20 35 11 25

API Response (JSON)

{
  "problem": {
    "name": "B. Producing Snow",
    "description": {
      "content": "Alice likes snow a lot! Unfortunately, this year's winter is already over, and she can't expect to have any more of it. Bob has thus bought her a gift — a large snow maker. He plans to make some amoun",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF947B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice likes snow a lot! Unfortunately, this year's winter is already over, and she can't expect to have any more of it. Bob has thus bought her a gift — a large snow maker. He plans to make some amoun...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments