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
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#define MAX_N 200002

using namespace std;
struct Group
{
	Group *p;
	unsigned long long int size;
	unsigned long long int start_time;
	unsigned long long int start_index;
	unsigned long long int end_index;
	Group(unsigned long long int size,unsigned long long int start_time,unsigned long long int start_index,unsigned long long int end_index):size(size),start_time(start_time),start_index(start_index),end_index(end_index),p(nullptr){}
	Group(){}
};

Group groups[MAX_N];
unsigned long long int client_time[MAX_N];
unsigned long long int sum[MAX_N];
unsigned int n,m;
unsigned long long int sum_d=0;
unsigned long long int diff=0;
set<pair<long long int,int>> event;
Group* parent(Group *a)
{
	Group* cur = a;
	if(cur->p != nullptr)
		cur->p = parent(cur->p);
	else return cur;
	return cur->p;
}	
bool merge(Group &a,Group &b) // left a 
{
	Group *pa=parent(&a);
	Group *pb=parent(&b);
	if(pa == pb)return false;
	//cout << diff << " " << sum_d << " " << pb->size << " " << pa->size << " "<< pb->start_time << " " << pa->start_time << "\n";
	diff += pb->size*(pb->start_time - pa->start_time);
	sum_d += sum[pa->size+pb->size-1] - sum[pa->size-1] - sum[pb->size-1];
	//cout << diff << " " << sum_d << "\n";
	pb->p=pa;
	pa->size+=pb->size;
	//pa->end_index = pb->end_index;
	pa->end_index = max(pa->end_index,pb->end_index);
	pa->start_index = min(pa->start_index,pb->start_index);
	pa->start_time = min(pa->start_time,pb->start_time);
	return true;
}


void init()
{
	for(int i=1;i<MAX_N;++i)
		sum[i] = sum[i-1]+i;
	
}
vector<long long int> cookingTime;
bool cmp(const int a,const int b)
{
	return cookingTime[a] < cookingTime[b];
}
int main()
{
	 std::ios::sync_with_stdio(false);
	init();
	long long int d;
	cin >> n >> m;
	groups[0] = Group(1,0,0,0);
	for(int i=1;i<=n;++i)
	{
		cin >> client_time[i];
		groups[i] = Group(1,client_time[i],i,i);
		long long int dt = client_time[i]-client_time[i-1];
		event.insert(make_pair(dt,i));//[dt] = i;
	}
	cookingTime.resize(m);
	for(int i=0;i<m;++i)
	{
		cin >> d;
		cookingTime[i] = d;
	}

	vector<int> pos(m);
	vector<long long int> res(m);
	for(int i=0;i<m;++i)
		pos[i]=i;
	
	sort(pos.begin(),pos.end(),cmp);
	for(auto p : pos)
	{
		long long int it = cookingTime[p];
		
			while(event.begin() != event.end()&& event.begin()->first<=it)
			{
				int idx = event.begin()->second;
				if(merge(groups[idx-1],groups[idx])){
		
					int end_index = parent(&groups[idx-1])->end_index;
					if(end_index<n)
					{
						long long int dt = client_time[end_index+1] - parent(&groups[idx-1])->start_time;
						long long int newTime = (dt)/(parent(&groups[idx-1])->size);
						if((dt)%(parent(&groups[idx-1])->size))newTime++;
						event.insert(std::pair<long long int,int>(newTime,end_index+1));
					}
				}
				event.erase(event.begin());
			}
			res[p] = it*sum_d-diff;
	}
	for(auto it : res)
		cout << it << "\n";
}