# codeforces - 948C

Posted by WildCow on March 15, 2018

# Producing Snow

Time Limit: 1000MS
Memory Limit: 256 megabytes

### Description

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 Vi 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 Ti, each pile will reduce its volume by Ti. 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 ≤ 10^5) — the number of days.

The second line contains N integers V1, V2, …, VN (0 ≤ Vi ≤ 10^9), where Vi is the initial size of a snow pile made on the day i.

The third line contains N integers T1, T2, …, TN (0 ≤ Ti ≤ 10^9), where Ti 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.

3
10 10 5
5 7 2

### Sample Output

5 12 4

``````
#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100010;

int ma[N];
int mb[N];
LL mc[N];
LL cnt1[N];
int cnt2[N];
int n;
int cnt;

int main(int argc, char const *argv[])
{
while(scanf("%lld", &n) == 1){
ma = mb = 0;
cnt = 1;
memset(cnt1, 0, sizeof(cnt1));
memset(cnt2, 0, sizeof(cnt2));
for(int i = 1; i <= n; i ++){
scanf("%d", &ma[i]);
}
for(int i = 1; i <= n; i ++){
scanf("%lld", &mb[i]);
mc[i] = mb[i];
mc[i] += mc[i - 1];
}
for(int i = 1; i <= n; i ++){
int l, r;
int ans;

l = i;
r = n;
ans = -1;
while(l <= r){
int mid;

mid = (l + r) >> 1;
if(mc[mid] - mc[i - 1] < ma[i]){
l = mid + 1;
}
else{
r = mid - 1;
ans = mid;
}
}
if(ans != -1){
cnt1[ans] -= (ma[i] - mc[ans] + mc[i - 1]);
cnt2[ans] ++;
}
}
for(int i = 1; i <= n; i ++){
printf("%lld ", 1ll * cnt * mb[i] - cnt1[i]);
cnt ++;
cnt -= cnt2[i];
}
printf("\n");
}

return 0;
}
``````