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.

Sample Input

3
10 10 5
5 7 2

Sample Output

5 12 4


刚开始觉得是一个题意杀

后来觉得其实很好理解的
总觉得似曾相识

一个人每天都要堆一个重量为 ma[i] 的雪人
每天每堆雪人都会融化 mb[i]
对于同一天是先堆雪人后融化
当然如果一个雪人已经没了肯定就不会再融化了

最后让你输出每天共融化了多少重量的雪

刚开始想着往数据结构方面去想
毕竟雪人的融化可以当作区间减
但是失败了= =

然后开始重新想
下意识的觉得应该来一个前缀和
然后就出来了

首先要知道一点

如果每个雪人体积是无限的
那么第 i 天融化的雪就是 mb[i] * i

然后有两个点会影响这个值

第一就是如果之前已经有雪人融化了,那么

我们对每天融化的雪来做一个前缀和

然后对于第 i 天堆其来的雪人
我们尝试去求出它在第几天会彻底融化

怎么求呢

当然是对于 (ma[i] + sum_mb[i 1]) 在 sum_mb 中二分啦

找到 sum_mb 中第一个大于他的数的下标 x
这就意味着在第 x 天这个雪人融化了

那么在那一天融化的雪就是 cnt * mb[x] - (sum_mb[x] - ma[i])
注意到这边用的是 cnt
因为有雪人融化
所以我们还要维护一下当前存在的雪人的个数

最后很显然会爆 int
比赛的时候懒得思考了
全换了 longlong!


#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[0] = mb[0] = 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;
}