1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;

struct event{
	int mach;
	int set1;
	int set2;
	event(int m, int s1, int s2) : mach(m), set1(s1), set2(s2) {}
	bool operator<(const event& a) const{
		return this->mach < a.mach;
	}
};

vector<long long> T;
vector<long long> K;
int group[250002];
int endd[250002];
bool visited[250002];
bool visited2[250002];
long long size[250002];
long long pref_sum[250002];

int binsercz(long long size, long long len, int st, int end){
	if(end <= st) return end;
	int x = (st + end)/2;
	if(K[x] * size >= len){
		return binsercz(size, len, st, x);
	}
	else{
		return binsercz(size, len, x+1, end);
	}
}

int main(){
	int n,m; scanf("%d %d", &n, &m);
	T.resize(n+1, 0);
	K.resize(m, 0);
	vector<pair<long long, int> > S;
	for(int i = 1; i <= n; i++){
		scanf("%lld", &T[i]);
	}
	pref_sum[0] = 0;
	for(int i = 1; i <= n; i++){
		pref_sum[i] = T[i] + pref_sum[i-1];
	}
	for(int i = 0; i < m; i++){
		long long x; scanf("%lld", &x);
		S.push_back(make_pair(x, i));
	}
	sort(S.begin(), S.end());
	int map[m];
	for(int i = 0; i < m; i++){
		map[S[i].second] = i;
		K[i] = S[i].first;
	}
	long long a,b;
	a = b = 0;
	for(int i = 0; i <= n; i++){
		visited[i] = 0;
		group[i] = i;
		size[i] = 1;
		endd[i] = i;
	}
	priority_queue<event> q;
	for(int i = 0; i < n; i++){
		long long r = T[i+1] - T[i];
		auto x = lower_bound(K.begin(), K.end(), r + 1);
		int pos = x - K.begin();
		if(pos != m){
			q.push(event(-pos, i, i+1));
		}
	}

	int last_considered = 0;
	vector<long long> results;

	int times = 0;
	int times2 = 0;
	while(!q.empty()){
		times++;
		event top = q.top();
		q.pop();
		int mach = -top.mach;
		if(visited2[top.set1]) continue;
		for(int i = 0; i < mach - last_considered; i++){
			//cout<<last_considered + i<<"  "<<K[last_considered + i]<<"   "<<a + (K[last_considered + i] * b)<<endl;
			results.push_back(a + (K[last_considered + i] * b));
		}
		//cout<<"dlugosc skoku : "<<K[mach]<<" grupa pierwsza : "<<group[top.set1]<<" grupa druga : "<<group[top.set2]<<endl;
		last_considered = mach;
		int set1 = group[top.set1];
		int set2 = group[top.set2];
		visited2[group[set2]] = 1;
		if(!visited[group[set2]] && (set1 < set2)){
			visited[group[set2]] = 1;
			a -= ((size[group[set1]] - 1) * T[group[set1]] - (pref_sum[endd[group[set1]]] - pref_sum[group[set1]]));
			a -= ((size[group[set2]] - 1) * T[group[set2]] - (pref_sum[endd[group[set2]]] - pref_sum[group[set2]]));
			b -= (size[group[set1]] - 1) * (size[group[set1]])/2;
			b -= (size[group[set2]] - 1) * (size[group[set2]])/2;
			endd[group[set1]] = endd[group[set2]];
			size[group[set1]] += size[group[set2]];
			//cout<<size[group[set1]]<<endl;
			a += ((size[group[set1]] - 1) * T[group[set1]] - (pref_sum[endd[group[set1]]] - pref_sum[group[set1]]));
			b += (size[group[set1]] - 1) * (size[group[set1]])/2;
			group[set2] = group[set1];
			if(endd[group[set1]] != n){
				long long diff = T[endd[group[set1]]+1] - T[group[set1]] + 1;
				int ind = binsercz(size[group[set1]], diff, mach, m);
				if(ind < m){
					//cout<<"wrzucam : "<<K[ind]<<"   "<<group[set1]<<"  "<<endd[group[set1]] + 1<<endl;
					q.push(event(-ind, group[set1], endd[group[set1]]+1));
				}
			}
		}
	}
	for(int i = 0; i < m - last_considered; i++)
		results.push_back(a + (K[last_considered + i] * b));
	for(int i = 0; i < results.size(); i++){
		printf("%lld\n", results[map[i]]);
	}	
	//cout<<times<<" "<<times2<<endl;
	//cout<<n<<"  "<<m<<endl;
}