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
#include <algorithm>
#include <iostream>
#include <stdint.h>
#include <vector>

struct bundle {
    int64_t start;
    uint64_t last_price;
    int count;
};

bool bundle_by_start(const bundle& fst, const bundle& snd) {
    return fst.start < snd.start;
}

struct query {
    int io_order;
    int64_t time;
    int64_t result;
};

bool query_by_io(const query& fst, const query& snd) {
    return fst.io_order < snd.io_order;
}

bool query_by_time(const query& fst, const query& snd) {
    return fst.time < snd.time;
}

std::vector<bundle> bundles;
int64_t triangular[200000];

int64_t calculate(int64_t prev_bake, int64_t bake_time) {
    int64_t bake_increment = bake_time - prev_bake;

    for (int i = 0; i < bundles.size(); i++) {
        bundle &bndl = bundles[i];
        bndl.start -= bake_increment;
        bndl.last_price += bake_increment * triangular[bndl.count - 1];

        if (bndl.start < 0) {
            bndl.last_price += (-bndl.start) * bndl.count;
            bndl.start = 0;
        }
    }

    int64_t total_time = 0;
    int in_bundle = 0, out_bundle = 0;
    while (in_bundle < bundles.size()) {
        bundle &i_bndl = bundles[in_bundle];
        bundle &o_bndl = bundles[out_bundle];

        o_bndl.start = i_bndl.start;
        o_bndl.last_price = i_bndl.last_price;
        o_bndl.count = i_bndl.count;

        int64_t bndl_end = o_bndl.start + o_bndl.count * bake_time;

        in_bundle += 1;
        while (in_bundle < bundles.size() && bundles[in_bundle].start <= bndl_end) {
            bundle &n_bndl = bundles[in_bundle];
            int64_t move_right = bndl_end - n_bndl.start;
            bndl_end += n_bndl.count * bake_time;
            o_bndl.count += n_bndl.count;
            o_bndl.last_price += n_bndl.last_price + move_right * n_bndl.count;
            in_bundle += 1;
        }

        total_time += o_bndl.last_price;
        out_bundle += 1;
    }

    while (out_bundle < bundles.size()) {
        bundles.pop_back();
    }

    return total_time;
}

int main() {
    int n, m;
    std::cin >> n >> m;

    for (int i = 1; i < 200000; i++) {
        triangular[i] = triangular[i-1] + i;
    }

    for (int i = 0; i < n; i++) {
        bundle bndl;
        bndl.last_price = 0;
        bndl.count = 1;

        std::cin >> bndl.start;
        bundles.push_back(bndl);
    }

    std::sort(bundles.begin(), bundles.end(), bundle_by_start);

    std::vector<query> queries;

    for (int i = 0; i < m; i++) {
        query q;
        q.io_order = i;
        q.result = 0;
        std::cin >> q.time;
        queries.push_back(q);
    }

    std::sort(queries.begin(), queries.end(), query_by_time);

    int64_t prev_time = 0;
    for (int i = 0; i < m; i++) {
        queries[i].result = calculate(prev_time, queries[i].time);
        prev_time = queries[i].time;
    }

    std::sort(queries.begin(), queries.end(), query_by_io);

    for (int i = 0; i < m; i++) {
        std::cout << queries[i].result << std::endl;
    }
}