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
126
127
128
129
130
131
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>

using std::vector;

template<typename T>
vector<T> readVect(int n) {
    vector<T> res;
    res.reserve(n);
    for (int i = 0; i < n; i++) {
        T a;
        std::cin >> a;
        res.push_back(a);
    }
    return res;
}

template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {
    // initialize original index locations
    vector<size_t> idx(v.size());
    iota(idx.begin(), idx.end(), 0);

    // sort indexes based on comparing values in v
    sort(idx.begin(), idx.end(),
    [&v](size_t i1, size_t i2) {
        return v[i1] < v[i2];
    });

    return idx;
}

void brutal(const vector<int64_t>& t, const vector<int>& d) {
    for (int j = 0; j < d.size(); j++) {
        int64_t minNextStart = 0;
        int64_t sum = 0;
        for (int i = 0; i < t.size(); i++) {
            int64_t wait = std::max(0ll, (minNextStart + d[j]) - t[i]);
            sum += wait;
            minNextStart = t[i] + wait;
        }
        std::cout << sum << "\n";
    }
}

struct Group {
    int64_t t_beg;
    int count;
    int nextGroup;  // sorry

    void append(Group& next) {
        count += next.count;
        nextGroup = next.nextGroup;
        if (next.count == 0)
            int aaa = 0;
        next.count = 0;   // critical, sorry^2
    }
};

void brutal_inny(const vector<int64_t>& t, const vector<int>& d) {
    vector<int64_t> sums;
    sums.resize(d.size());

    vector<Group> groups;
    groups.reserve(t.size() + 1);

    groups.push_back({0LL, 1, 1});
    for (int i = 0; i < t.size(); i++) {
        groups.push_back({t[i], 1, groups.size() + 1});
    }

    std::priority_queue< std::pair<int64_t, int> > pq;  // pri + group index
    for (int i = 0; i < groups.size()-1; i++) {
        int64_t gap = groups[i + 1].t_beg - groups[i].t_beg;
        pq.push(std::make_pair(-gap, i));
    }
    pq.push(std::make_pair(-1e18, -1));

    int64_t d_mul = 0;
    int64_t sum_delta_tk = 0;
    // d * L*(L-1)/2 - sum_delta_tk;
    for (auto j : sort_indexes(d)) {
        auto dj = d[j];
        while (-pq.top().first < dj) {
            int groupIndex = pq.top().second;
            pq.pop();

            Group& ga = groups[groupIndex];
            if (ga.count == 0)
                continue;  // already merged

            Group& gb = groups[ga.nextGroup];

            d_mul += ga.count * int64_t(gb.count);
            sum_delta_tk += (gb.t_beg - ga.t_beg) * gb.count;

            ga.append(gb);

            if (gb.nextGroup != groups.size()) {
                int64_t gap = groups[gb.nextGroup].t_beg - ga.t_beg;
                gap /= ga.count;  // merged count
                pq.push(std::make_pair(-gap, groupIndex));
            }
        }
        sums[j] = dj * d_mul - sum_delta_tk;
    }

    for (int j = 0; j < d.size(); j++) {
        std::cout << sums[j] << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(0);
    // freopen("path", "r", stdin);

    int n, m;  // 1 <= n, m <= 200 000
    std::cin >> n >> m;

    vector<int64_t> t = readVect<int64_t>(n);  // <= 10^12
    vector<int> d = readVect<int>(m);  // <= 10^6

    // d = std::vector<int>(&d[0],&d[20]);

    // brutal(t, d);
    //std::cout << "---" <<std::endl;
    brutal_inny(t, d);
}