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
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <list>

struct client_cluster {
    long long clients;
    long long cluster_spread;
    long long first_client;
    long long last_client;

    client_cluster(long long number_of_clients, long long first_client, long long last_client) : clients(number_of_clients),
                                                                        first_client(first_client),
                                                                        last_client(last_client) {
        cluster_spread = 0;
    }
};

struct ov_idx {
    long long value;
    int idx;
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n, m;
    std::cin >> n >> m;

    std::list<client_cluster> clients;
    std::vector<ov_idx> ovens(m);

    for (int i = 0; i < n; i++) {
        long long client_time;
        std::cin >> client_time;
        clients.emplace_back(1, client_time, client_time);
    }

    for (int i = 0; i < m; i++) {
        std::cin >> ovens[i].value;
        ovens[i].idx = i;
    }

    auto cmp = [](const ov_idx& a, const ov_idx& b) {
        return a.value < b.value;
    };

    std::sort(ovens.begin(), ovens.end(), cmp);
    std::vector<long long> res(m);

    for (int j = 0; j < m; j++) {
        long long bake_time = ovens[j].value;
        long long waiting = 0;

        auto cl_iter = clients.begin();
        auto prev_iter = clients.begin();
        long long last_free = 0;
        while (cl_iter != clients.end()) {
            client_cluster &next_client = *cl_iter;
            long long clients_number = next_client.clients;
            long long clients_number_minus_one = clients_number - 1;
            long long free_time = next_client.first_client - last_free;
            long long client_time_separation = bake_time - free_time;
            long long cli_wait = std::max(0LL, client_time_separation);
            long long sum = clients_number * (clients_number_minus_one) / 2;

            waiting += sum * bake_time - next_client.cluster_spread
                       + cli_wait * clients_number;

            if (cl_iter != clients.begin() && client_time_separation >= 0) {
                //merge clusters
                long long dist = next_client.first_client - prev_iter->first_client;
                prev_iter->clients += clients_number;
                prev_iter->cluster_spread += next_client.cluster_spread + clients_number_minus_one * dist;
                prev_iter->cluster_spread += next_client.first_client - prev_iter->first_client;
                prev_iter->last_client = next_client.last_client;
                clients.erase(cl_iter++);

            } else
                prev_iter = cl_iter++;

            last_free = next_client.first_client + cli_wait + clients_number_minus_one * bake_time;
        }
        res[ovens[j].idx] = waiting;
    }
    for (auto &&item : res) {
        std::cout << item << std::endl;
    }
}