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
#include<stdio.h>
#include<algorithm>
#include<utility>
#include<set>
#include<cstring>

using namespace std;

const int N=200001;
long long people[N];
pair<int,int> times[N];
long long results[N];
const int inftyPos=N+1;
int zlsize=0;

struct setEl;

struct zlepek {
    int left;
    long long middle;
    int right;
    int pos;
    int nextpos;
    multiset<setEl>::iterator setit;
    zlepek() {}
    zlepek(int x, long long w, int y, int z, int v): left(x), middle(w), right(y), pos(z), nextpos(v) {}
    double time();
} zlepki[N];

double zlepek::time() {
   if (nextpos < zlsize)
      return (zlepki[nextpos].middle-middle)/((double)right+1);
   return -1;
}

struct setEl {
    int pos;
    setEl(int p): pos(p) {}
    bool operator < (setEl const& z) const {
        return zlepki[pos].time() < zlepki[z.pos].time();
    }
};

multiset<setEl> pq;

int n,m;

void zlep(int p1, int p2) {
    zlepki[p1].nextpos=zlepki[p2].nextpos;
    zlepki[p1].right+=zlepki[p2].right+1;
    pq.erase(zlepki[p1].setit);
    if(zlepki[p2].setit!=pq.end()) {
        pq.erase(zlepki[p2].setit);
        zlepki[p1].setit=pq.insert(setEl(p1));
    }
    else zlepki[p1].setit=pq.end();
}

long long sum(long long k) { return k*(k+1)/2; }

int main() {
    scanf("%d %d",&n,&m);
    for(int i=0; i<n; ++i) scanf("%lld",people+i);
    for(int i=0; i<m; ++i) {
        int d;
        scanf("%d",&d);
        times[i]=make_pair(d,i);
    }
    sort(times,times+m);
    zlepki[0]=zlepek(1,0,0,0,1);
    for(int i=0; i<n; ++i) {
        if(people[i]==zlepki[zlsize].middle) zlepki[zlsize].right++;
        else zlepki[++zlsize]=zlepek(1,people[i],0,zlsize,zlsize+1);
    }
    ++zlsize;

    for(int i=0; i<zlsize-1; ++i) zlepki[i].setit=pq.insert(setEl(i));
    zlepki[zlsize-1].setit=pq.end();

    int d1=0;
    long long total=0;
    long long s=0;
    for(int i=0; i<zlsize; i++)
        s+=sum(zlepki[i].right);
    for(int i=0; i<m; i++) {
        int d2 = times[i].first;
        total-=s*d1;
        while(!pq.empty()){
            int p1=pq.begin()->pos;
            if(zlepki[p1].time()>d2) break;
            int p2=zlepki[p1].nextpos;
            long long dt=zlepki[p2].middle-zlepki[p1].middle;
            int k1=zlepki[p1].right;
            int k2=zlepki[p2].right;
            s-=sum(k1)+sum(k2);
            s+=sum(k1+k2+1);
            total-=dt*(k2+1);
            zlep(p1,p2);
        }
        total+=s*d2;
        results[times[i].second]=total;
        d1=d2;
    }
    for(int i=0; i<m; ++i) printf("%lld\n",results[i]);

    return 0;
}