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
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>


struct Node {
	long long n = 0;
	long long idxSum = 0;
};

const int MAX = 200200;
int n, m;
long long t[MAX];
int d[MAX];
std::map<int, long long> pRes;
std::map<long long, Node> groups;
std::map<long long, std::vector<std::pair<long long, long long> > > q;


int main(int argc, char *argv[]) {
	scanf("%i%i", &n, &m);
	t[0] = 0;
	for (int c = 1; c <= n; c++) {
		scanf("%lli", t + c);
	}
	for (int c = 0; c < m; c++) {
		scanf("%i", d + c);
		pRes[d[c]] = 0;
	}

	auto addJoin = [](long long tPrev, long long start) {
		long long diff = start - tPrev;
		long long join = (diff / groups[tPrev].n) + 1;
		q[join].push_back(std::pair<long long, long long>(tPrev, start));
	};

	long long tPrev = -1;
	for (int c = 0; c <= n; c++) {
		long long start = t[c];
		groups[start].n++;
		//groups[start].tStart = start;

		if (tPrev != -1 && tPrev != start) {
			addJoin(tPrev, start);
		}
		tPrev = start;
	}

	long long nTotal = 0;
	long long idxSumTotal = 0;
	for (auto &sg : groups) {
		nTotal += sg.second.n * (sg.second.n - 1) / 2;
	}

	for (auto iter = pRes.begin(); iter != pRes.end(); iter++) {
		int pTime = iter->first;

		while (!q.empty() && q.begin()->first <= pTime) {
			long long tPrev = q.begin()->second.back().first;
			long long start = q.begin()->second.back().second;
			q.begin()->second.pop_back();
			if (q.begin()->second.empty()) {
				q.erase(q.begin());
			}

			if (groups.count(tPrev) > 0 && groups.count(start) > 0) {
				auto &g1 = groups[tPrev];
				auto &g2 = groups[start];
				nTotal -= g1.n * (g1.n - 1) / 2;
				nTotal -= g2.n * (g2.n - 1) / 2;
				idxSumTotal -= g1.idxSum;
				idxSumTotal -= g2.idxSum;

				g1.n += g2.n;
				g1.idxSum += (start - tPrev) * g2.n + g2.idxSum;
				groups.erase(start);

				nTotal += g1.n * (g1.n - 1) / 2;
				idxSumTotal += g1.idxSum;

				auto iNext = groups.lower_bound(tPrev);
				if (++iNext != groups.end()) {
					addJoin(tPrev, iNext->first);
				}
			}
		}

		pRes[pTime] = nTotal * pTime - idxSumTotal;
	}

	for (int c = 0; c < m; c++) {
		printf("%lli\n", pRes[d[c]]);
	}
	return 0;
}