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

typedef long long ll;
const int N = 2e5 + 5;
int n, m, nast[N];
ll ans[N], t[N], kro[N];
pair<ll,int> d[N];
bool wyrzuc[N];

int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++)
    scanf("%lld", &t[i]);
  t[n] = 0; n++;
  for (int i = 0; i < m; i++)
  {
    scanf("%lld", &d[i].first);
    d[i].second = i;
  }

  sort(t, t+n);
  sort(d, d+m);

  ll minusy = 0, sumka = 0;
  priority_queue<pair<ll,int>> Q;
  for (int i = 0; i < n-1; i++)
  {
    kro[i] = 1;
    nast[i] = i+1;
    Q.push({-(t[i+1] - t[i] + 1), i});
  }
  kro[n-1] = 1;

  for (int i = 0; i < m; i++)
  {
    while (!Q.empty() && -Q.top().first <= d[i].first)
    {
      int p = Q.top().second; Q.pop();

      if (wyrzuc[p] || nast[p] == 0) continue;
      ll val = (t[nast[p]] - t[p]) / kro[p] + 1;
      if (val > d[i].first) continue;

      minusy += kro[nast[p]] * (t[nast[p]] - t[p]);
      sumka -= kro[p] * (kro[p] - 1) / 2LL;
      sumka -= kro[nast[p]] * (kro[nast[p]] - 1) / 2LL;

      wyrzuc[nast[p]] = 1;
      kro[p] += kro[nast[p]];

      sumka += kro[p] * (kro[p] - 1) / 2LL;

      nast[p] = nast[nast[p]];
      if (nast[p] != 0)
        Q.push({-((t[nast[p]] - t[p]) / kro[p] + 1), p});
    }

    ans[d[i].second] = d[i].first * sumka - minusy;
  }

  for (int i = 0; i < m; i++)
    printf("%lld\n", ans[i]);

  return 0;
}