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
// PA2017, Zapiekanki 2
// Andrzej Pezarski

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

struct Ziomek {
    long long t;
    int next;
    bool active;
};


int N, M;
Ziomek ziomek[210000];
long long res[210000];
long long sumaZ=0;
long long sumaD=0;

int main() {
    int N,M;
    scanf("%d%d", &N, &M);
    ziomek[0].t=0;
    ziomek[0].next=1;
    ziomek[0].active=true;
    for(int i=1; i<=N; i++) {
        scanf("%lld", &(ziomek[i].t));
        ziomek[i].next=1;
        ziomek[i].active=true;
    }
    N++;
    priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > Q;
    
    for(int i=0; i<M; i++) {
        long long d;
        scanf("%lld", &d);
        Q.push(make_pair(d, i+N));
    }

    for(int i=0; i<N-1; i++) {
        Q.push(make_pair(ziomek[i+1].t-ziomek[i].t, i));
    }
    
    int resM=M;

    while(resM) {
        long long d=Q.top().first;
        int i=Q.top().second;
        Q.pop();
//        printf("--> %lld  %d  %lld  %lld\n", d, i, sumaD, sumaZ);
        if (i<N) {
            if (!ziomek[i].active) continue;
            int j=i+ziomek[i].next;
            ziomek[j].active=false;
            sumaD-=1LL*ziomek[i].next*(ziomek[i].next-1)/2;
            sumaD-=1LL*ziomek[j].next*(ziomek[j].next-1)/2;
            ziomek[i].next+=ziomek[j].next;
            sumaD+=1LL*ziomek[i].next*(ziomek[i].next-1)/2;
            sumaZ+=(ziomek[j].t-ziomek[i].t)*ziomek[j].next;
            
            j=i+ziomek[i].next;
            if (j<N) Q.push(make_pair((ziomek[j].t-ziomek[i].t)/(j-i)+1, i));
        } else {
            i-=N;
            resM--;
            res[i]=sumaD*d- sumaZ;
        }
    }
    for(int i=0; i<M; i++) printf("%lld\n", res[i]);
    return 0;
}