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 #include #include #include #include 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 clients; std::vector 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 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; } }