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
#define LL long long
#include<stdio.h>
#include<bits/stdc++.h>

using namespace std;

int m, n;  // ilosci klientow, kuchenek
LL T[200000];  //  przybycia klientow
LL D[200000];  //  czasy pracy kuchenek  
LL K[200000];  //  czasy pracy kuchenek, posortowane 
LL czasy[200000];  //  sumaryczne czasy oczekiwania klientow dla poszczegolnych czasow pieczenia z tabeli K[]
map<LL, LL> czas_czekania;

LL czekanie(LL pieczenie)  {
	LL wolna_od = 0;
	LL czas = 0;  // czas czekania
	
	for(int i =0; i < n; i++) {
		wolna_od += pieczenie;
		if (T[i] > wolna_od) wolna_od = T[i];
		czas += wolna_od - T[i];
	}
	
	return czas;
}

void obliczenia(int imin, int imax){

	if(imax-imin<2) return;
	if(czasy[imax]==czasy[imin]) {
		for(int j=imin+1; j<imax;j++) czasy[j]=czasy[imin];
		return;
	}

	while(K[imin]==K[imin+1]){
		czasy[imin+1]=czasy[imin];
		imin++;
	}
	while(K[imax]==K[imax-1]){
		czasy[imax-1]=czasy[imax];
		imax--;
	}
	if(imax-imin<2) return;
	int centrum = (imin+imax)/2;
	czasy[centrum]=czekanie(K[centrum]);
	obliczenia(imin,centrum);
	obliczenia(centrum,imax);
	
}




int main()  {
	
	scanf("%d", &n);
	scanf("%d", &m);
	
	for(int i=0; i < n; i++)  {
		scanf("%lld", T + i);
	}
	
	for(int i=0; i < m; i++)  {
		scanf("%lld", D + i);
		K[i] = D[i];
	}
	sort(K, K+m);

	
	// obliczenia
	czasy[0] = czekanie( K[0] );
	czasy[m-1] = czekanie( K[m-1] );
	obliczenia(0,m-1);
	
   
	for(int i = 0; i < m; i++) {
		czas_czekania[K[i]] = czasy[i];
	}
	
	
    // wyniki
    for(int i = 0; i < m; i++){
    	printf("%lld \n", czas_czekania[D[i]]);
   }
	
	return 0;
}