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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
using namespace std;

#define ull  unsigned long long
#define ll  long long

class G
{
public:
    ll bt;
    ll count;
    ll sumT;
    ll d;
    G* next;

    G() {}

    void Set(G *n, ll dist)
    {
        sumT = 0;
        count = 1;
        d = dist;
        next = n;
    }
};

struct comp
{
    bool operator() (G* gl, G* gh) const
    {
        if (gl->d < gh->d)
            return true;
        if (gl->d == gh->d && gl < gh)
            return true;
        return false;
    }
};

G timex[200001];

int main()
{
    set<G*, comp> gr;

    set<ll> cookTimes;
    set<ll>::iterator cookIter;
    unordered_map<ll, ll> sol;

    int n = 0;
    int m = 0;
    scanf("%i %i", &n, &m);

    timex[0].bt = 0;
    for (ll i = 1; i <= n; ++i)
    {
        scanf("%lld", &(timex[i].bt));
    }

    ll *owen = new ll[m];
    for (ll i = 0; i < m; ++i)
    {
        scanf("%lld", &owen[i]);
        cookTimes.insert(owen[i]);
    }

    timex[n].Set(NULL, 1000000000000);
    gr.insert(&timex[n]);
    for (ll i = n - 1; i >= 0; --i)
    {
        timex[i].Set(&timex[i + 1], timex[i + 1].bt - timex[i].bt);
        gr.insert(&timex[i]);
    }

    G *g1, *g2;
    ll cookMulti = 0;
    ll timeCount = 0;
    ll cookTime = 0;
    while (!cookTimes.empty())
    {
        cookIter = cookTimes.begin();
        cookTime = (*cookIter);

        while ((*gr.begin())->d < cookTime)
        {
            g1 = (*gr.begin());
            g2 = g1->next;

            cookMulti -= (g1->count * (g1->count - 1)) / 2;
            cookMulti -= (g2->count * (g2->count - 1)) / 2;
            timeCount -= g1->sumT;
            timeCount -= g2->sumT;

            g1->count += g2->count;
            g1->sumT += g2->sumT + g2->count * (g2->bt - g1->bt);
            if (g2->next != NULL)
                g1->d = (g2->next->bt - g1->bt) / g1->count;
            else
                g1->d = g2->d;
            g1->next = g2->next;

            cookMulti += (g1->count * (g1->count - 1)) / 2;
            timeCount += g1->sumT;

            gr.erase(gr.begin());
            gr.erase(g2);
            gr.insert(g1);
        }

        sol[cookTime] = cookMulti * cookTime - timeCount;
        cookTimes.erase(cookIter);
    }

    for (ll i = 0; i < m; ++i)
    {
        printf("%lld\n", sol[owen[i]]);
    }

    return 0;
}