#include <algorithm> #include <iostream> #include <set> #include <vector> #include <cassert> constexpr int64_t INF = 1e18; struct Block { Block* next{nullptr}; int64_t begin{0}, count{1}; int64_t order{0}; void update(int64_t piece) { if (!next) { order = INF; return; } int64_t dist = next->begin - begin - count*piece; order = (dist + piece*count) / count; } }; struct BlockCmp { bool operator()(Block* l, Block* r) const { return l->order < r->order || (l->order == r->order && l < r); } }; std::vector<int64_t> clients, options; std::vector<int64_t*> optionsSorted; std::vector<Block> blocks; std::set<Block*, BlockCmp> que; int64_t current = 0, scaled = 0; int64_t compute(int64_t piece) { while (true) { assert(!que.empty()); Block* block = *que.begin(); if (block->order >= piece) { break; } Block* next = block->next; assert(next); que.erase(que.begin()); que.erase(next); // Merge blocks scaled -= block->count * (block->count-1) / 2; scaled -= next->count * (next->count-1) / 2; current += next->count * (next->begin-block->begin); block->count += next->count; block->next = next->next; block->update(piece); scaled += block->count * (block->count-1) / 2; que.insert(block); } return scaled*piece - current; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int nClients, nOptions; std::cin >> nClients >> nOptions; clients.resize(nClients+1); options.resize(nOptions); optionsSorted.resize(nOptions); for (int i = 1; i <= nClients; i++) { std::cin >> clients[i]; } for (int i = 0; i < nOptions; i++) { std::cin >> options[i]; optionsSorted[i] = &options[i]; } std::sort(optionsSorted.begin(), optionsSorted.end(), [](int64_t* l, int64_t* r)->bool { return *l < *r; }); // Init blocks blocks.resize(clients.size()); for (int i = blocks.size()-1; i >= 0; i--) { blocks[i].begin = clients[i]; blocks[i].next = (i+1 < int(blocks.size()) ? &blocks[i+1] : nullptr); blocks[i].update(0); que.insert(&blocks[i]); } // Compute for (int64_t* option : optionsSorted) { *option = compute(*option); } for (int64_t option : options) { std::cout << option << std::endl; } return 0; }
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 | #include <algorithm> #include <iostream> #include <set> #include <vector> #include <cassert> constexpr int64_t INF = 1e18; struct Block { Block* next{nullptr}; int64_t begin{0}, count{1}; int64_t order{0}; void update(int64_t piece) { if (!next) { order = INF; return; } int64_t dist = next->begin - begin - count*piece; order = (dist + piece*count) / count; } }; struct BlockCmp { bool operator()(Block* l, Block* r) const { return l->order < r->order || (l->order == r->order && l < r); } }; std::vector<int64_t> clients, options; std::vector<int64_t*> optionsSorted; std::vector<Block> blocks; std::set<Block*, BlockCmp> que; int64_t current = 0, scaled = 0; int64_t compute(int64_t piece) { while (true) { assert(!que.empty()); Block* block = *que.begin(); if (block->order >= piece) { break; } Block* next = block->next; assert(next); que.erase(que.begin()); que.erase(next); // Merge blocks scaled -= block->count * (block->count-1) / 2; scaled -= next->count * (next->count-1) / 2; current += next->count * (next->begin-block->begin); block->count += next->count; block->next = next->next; block->update(piece); scaled += block->count * (block->count-1) / 2; que.insert(block); } return scaled*piece - current; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int nClients, nOptions; std::cin >> nClients >> nOptions; clients.resize(nClients+1); options.resize(nOptions); optionsSorted.resize(nOptions); for (int i = 1; i <= nClients; i++) { std::cin >> clients[i]; } for (int i = 0; i < nOptions; i++) { std::cin >> options[i]; optionsSorted[i] = &options[i]; } std::sort(optionsSorted.begin(), optionsSorted.end(), [](int64_t* l, int64_t* r)->bool { return *l < *r; }); // Init blocks blocks.resize(clients.size()); for (int i = blocks.size()-1; i >= 0; i--) { blocks[i].begin = clients[i]; blocks[i].next = (i+1 < int(blocks.size()) ? &blocks[i+1] : nullptr); blocks[i].update(0); que.insert(&blocks[i]); } // Compute for (int64_t* option : optionsSorted) { *option = compute(*option); } for (int64_t option : options) { std::cout << option << std::endl; } return 0; } |