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
#include <cstdio>
#include <algorithm>
#include <set>
#include <queue>

long long tab[200007];
std::pair<int, int> d[200007];

std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> Q;
std::set<std::pair<long long, int>> s;

long long prawo[200007];
int ile[200007];
int poprz[200007];
long long obl[200007];
long long suml[200007];
long long wyniki[200007];
long long sumrel[200007];

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    s.insert({0, 0});
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &tab[i]);
        obl[i] = tab[i] - tab[i - 1];
        Q.push({obl[i], i});
        poprz[i] = i - 1;
        s.insert({tab[i], i});
        suml[i] = suml[i - 1] + i;
    }
    for (int i = 0; i < M; i++) {
        scanf("%d", &d[i].first);
        d[i].second = i;
    }
    std::sort(d, d + M);
    int q = 0;
    long long sum = 0;
    long long sum2 = 0;
    while (!Q.empty()) {
        long long zeit = Q.top().first;
        int ter = Q.top().second;
        Q.pop();
        if (obl[ter] != zeit)
            continue;
        while (q < M && zeit > d[q].first) {
            wyniki[d[q].second] = sum * d[q].first - sum2;
            q++;
        }
        obl[ter] = -1;
        s.erase({tab[ter], ter});
        int p = poprz[ter];
//        printf("Lacze %d z %d\n", p, ter);
        sum2 -= sumrel[ter];
        sum2 -= sumrel[p];
        sumrel[p] += (ile[ter] + 1) * (tab[ter] - tab[p]) + sumrel[ter];
        sum2 += sumrel[p];
        sum -= suml[ile[ter]];
        sum -= suml[ile[p]];
        ile[p] += ile[ter] + 1;
        sum += suml[ile[p]];
        prawo[p] = zeit * ile[p];
//        printf("ile = %d, prawo = %lld\n", ile[p], prawo[p]);
        auto next = s.upper_bound({tab[ter], ter});
        if (next != s.end()) {
            ter = next->second;
//            printf("Sprawdzam czas laczenia %d (%lld) z %d (%lld)\n", p, tab[p], ter, tab[ter]);
            long long odl = (tab[ter] - tab[p] - prawo[p] - zeit);
//            printf("Prawo[%d] = %lld, Lewo[%d] = %lld\n", p, prawo[p], ter, lewo[ter]);
//            printf("Odl = %lld\n", odl);
            long long czas = zeit + ((odl + ile[p]) / (ile[p] + 1));
            czas = std::max(czas, zeit);
            obl[ter] = czas;
            poprz[ter] = p;
//            printf("Wrzucam nowy czas %lld\n", czas);
            Q.push({czas, ter});
        }
    }
    while (q < M) {
        wyniki[d[q].second] = sum * d[q].first - sum2;
        q++;
    }
    for (int i = 0; i < M; i++) {
        printf("%lld\n", wyniki[i]);
    }
    return 0;
}