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;
}