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
#include <bits/stdc++.h>
using namespace std;

#define fru(j,n) for(int j=0; j<(n); ++j)
#define tr(it,v) for(auto it=(v).begin(); it!=(v).end(); ++it)
#define x first
#define y second
#define pb push_back
#define ALL(G) (G).begin(),(G).end()

#if 0
	#define DEB printf
#else
	#define DEB(...)
#endif

typedef long long ll;
typedef long long LL;
typedef double D;
typedef pair<int,int> pii;
typedef vector<int> vi;

const int inft = 1000000009;
const int mod = 1000000007;
const int MAXN = 200006,T=1024*1024;

ll t[MAXN],pt[MAXN];
ll C[2*T]; // ile aktualnie czeka
ll W[2*T]; // wyniki
ll W2[2*T]; // wyniki
void add(ll* tab,int a,int b,ll x){
	a+=T;b+=T;
	while(a<=b){
		if(a%2==1){tab[a]+=x;a++;}
		if(b%2==0){tab[b]+=x;b--;}
		a/=2;b/=2;
	}
}
ll get(ll *tab, int a){
	a+=T;
	ll ret=0;
	while(a){
		ret+=tab[a];
		a/=2;
	}
	return ret;
}
vector<pii> Q;
vector<pii> X;

bool waitt(int poz,int i){ //czy i-te zgloszenie czeka
	int wa=get(C,poz);
	DEB("czas piecz %d(val%d) czeka %d ##",poz,X[poz].x,wa);
	ll tim=1LL*(wa+1)*X[poz].x+(i-wa>0?t[i-wa-1]:0);
	DEB("lacznie %lld, poowinno %lld\n",tim,t[i]);
	return tim>t[i];
}

int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	fru(i,n)scanf("%lld",&t[i]);
	pt[0]=0;
	fru(i,n)pt[i+1]=pt[i]+t[i];
	X.resize(m);
	fru(i,m){
		scanf("%d",&X[i].x);
		X[i].y=i;
	}
	sort(ALL(X));
	Q.push_back(pii(m,0));
	t[n]=1LL<<50;
	fru(i,n+1){
		//find first that will wait:
		int p=0,k=m;
		if(waitt(0,i))k=0;
		while(k-p>1){
			int mid=(p+k)/2;
			if(waitt(mid,i))k=mid;
			else p=mid;
		}
		DEB("dodaje od %d(val%d)\n",k,X[k].x);
		add(C,k,m,1);
		int sum=0;
		while(Q.back().x<k){
			sum+=Q.back().y;
			int A=Q.back().x;
			Q.pop_back();
			int B=min(k,Q.back().x);
			// [A,B) dodaj do wyniku, kazdy czeka z sum
			DEB("zeruje przedzial [%d,%d) z %d\n",A,B,sum);
			add(C,A,B-1,-1LL*sum);//C -sumy na przedziale
			add(W,A,B-1,1LL*sum*(sum+1)/2);
			ll dt=pt[i]-pt[i-sum]-1LL*sum*(i-sum>0?t[i-sum-1]:0);
			DEB("czekaja %lld\n",dt);
			add(W2,A,B-1,dt);
		}
		sum++;
		if(Q.back().x==k)Q.back().y+=sum;
		else Q.push_back(pii(k,sum));
	}
	vector<ll> ANS(m);
	fru(i,m){
		ANS[X[i].y]=get(W,i)*X[i].x-get(W2,i);
	}
	fru(i,m)printf("%lld\n",ANS[i]);
	return 0;
}