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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define PB push_back
#define MP make_pair
#define ST first
#define ND second

ll *t;
pll *d;
ll *res;
struct Por {
    bool operator() (pair<pll,pll> a, pair<pll,pll> b)
    {
        if(a.ST.ST*b.ST.ND > b.ST.ST*a.ST.ND)
        {
            return true;
        }
        return false;
    }

};
priority_queue<pair<pll, pll>,  vector<pair<pll, pll>>, Por> kolejka;
ll sg=0, lg=0;
int *p, *nast;
ll *suma, *licz;
int n;


int findp(int a)
{
    if(p[a] == a)
        return a;
    p[a] = findp(p[a]);
    return p[a];
}

void uni(int x, int y)
{
    //cout << x << " " << y << endl;
    if(x==y)
        return;
    p[y] = x;
    sg-=(suma[x]+suma[y]);
    lg-=(licz[x]*(licz[x]-1)/2+licz[y]*(licz[y]-1)/2);
    suma[x] = suma[x] + suma[y] + licz[y]*t[x] - (licz[y])*t[y];
    licz[x] = licz[x] + licz[y];
    sg+=suma[x];
    lg+=licz[x]*(licz[x]-1)/2;
    int z = nast[y];
    nast[x] = z;
    if(z<=n)
        kolejka.push(MP(MP(t[z]-t[x], z-x), MP(x, z)));
}

int main()
{
    ios_base::sync_with_stdio(0);
    int m;
    cin >> n >> m;
    d = new pll[m];
    res = new ll[m];
    t = new ll[n+1];
    p = new int[n+1];
    nast = new int[n+1];
    suma = new ll[n+1];
    licz = new ll[n+1];
    for(int i=0; i <= n; i++)
    {
        p[i] = i;
        suma[i] = 0;
        licz[i] = 1;
        nast[i] = i+1;
    }
    t[0] = 0;
    for(int i=1; i <= n; i++)
        cin >> t[i];
    for(int i=0; i < m; i++)
    {
        cin >> d[i].ST;
        d[i].ND = i;
    }
    sort(d, d+m);
    for(int i=0; i< n; i++)
    {
        kolejka.push(MP(MP(t[i+1]-t[i], 1), MP(i, i+1)));
    }
    for(int k=0; k < m; k++)
    {
        ll dp = d[k].ST;
        while(kolejka.empty()==false)
        {
            pair<pll, pll> x = kolejka.top();
            if(x.ST.ST >= x.ST.ND*dp)
                break;
            kolejka.pop();
            uni(findp(x.ND.ST), findp(x.ND.ND));
        }
        res[d[k].ND] = sg + lg*dp;
    }

    for(int i=0; i < m; i++)
    {
        cout << res[i] << "\n";
    }
    return 0;
}