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
#include <cstdio>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <algorithm>

struct Group {
	int id;
	int numMembers;
	long long begin;
	long long sumOfDelays;
	Group *next;
	bool active;
};

long long whenInterfereWithNext(const Group &group) {
	// printf("Licznik: %lf, mianownik: %d, ułamek: %lf\n", ((double)group.next->begin - group.begin + 1), group.numMembers, ((double)group.next->begin - group.begin + 1) / group.numMembers);
	return ceil(((double)group.next->begin - group.begin + 1) / group.numMembers);
}

long long groupWaitingTime(const Group &group, int cookingTime) {
	return (long long) (group.numMembers - 1) * group.numMembers * cookingTime / 2 - group.sumOfDelays;
}

long long groupScalarSum(const Group &group) {
	return (long long) (group.numMembers - 1) * group.numMembers / 2;
}

void mergeGroups(Group *group) {
	// printf("Łączenie grupy: %d z groupą: %d\n", group->id, group->next->id);
	Group *next = group->next;
	group->numMembers += next->numMembers;
	group->sumOfDelays += next->sumOfDelays + (next->begin - group->begin) * next->numMembers;
	group->next = next->next;
	next->active = false;
}

int main() {
	int n, m;
	std::vector<long long> customers;
	std::vector<Group> groups;
	std::vector<std::pair<int, int>> cookingTimes;
	std::vector<std::pair<int, long long>> res;
	std::priority_queue<std::pair<long long, Group*>> interferenceQueue;

	scanf("%d%d", &n, &m);

	Group group;
	group.id = -1;
	group.numMembers = 1;
	group.sumOfDelays = 0;
	group.active = true;
	group.begin = 0;
	groups.push_back(group);
	for (int i = 0; i < n; ++i) {
		Group group;
		group.id = i;
		group.numMembers = 1;
		group.next = nullptr;
		group.sumOfDelays = 0;
		group.active = true;
		scanf("%lld", &group.begin);
		groups.push_back(group);
	}
	for (unsigned i = 0; i < groups.size() - 1; ++i) {
		groups[i].next = &groups[i+1]; 
		// printf("Grupa: %d zacznie interferować przy długości pieczenia: %lld\n", groups[i].id, whenInterfereWithNext(groups[i]));
		interferenceQueue.push(std::make_pair(-whenInterfereWithNext(groups[i]), &groups[i]));
	}

	for (int i = 0; i < m; ++i) {
		int cookingTime;
		scanf("%d", &cookingTime);
		cookingTimes.push_back(std::make_pair(cookingTime, i));
	}
	std::sort(std::begin(cookingTimes), std::end(cookingTimes));

	long long sumOfWaitingTimes = 0;
	long long scalarSum = 0;
	int prevCookingTime = 0;
	for (unsigned i = 0; i < cookingTimes.size(); ++i) {
		int cookingTime = cookingTimes[i].first;
		// printf("Cooking time: %d\n", cookingTime);
		int queryId = cookingTimes[i].second;
		int diffCookingTime = cookingTime - prevCookingTime;
		sumOfWaitingTimes += diffCookingTime * scalarSum;
		// printf("Pierwsza grupa zacznie interferować przy długości pieczenia: %lld\n", -interferenceQueue.top().first);
		while (!interferenceQueue.empty() && -interferenceQueue.top().first <= cookingTime) {
			std::pair<long long, Group*> elem = interferenceQueue.top();
			interferenceQueue.pop();
			Group *group = elem.second;
			if (!group->active) {
				continue;
			}
			
			sumOfWaitingTimes -= groupWaitingTime(*group, cookingTime);
			sumOfWaitingTimes -= groupWaitingTime(*(group->next), cookingTime);
			scalarSum -= groupScalarSum(*group);
			scalarSum -= groupScalarSum(*(group->next));
			mergeGroups(group);
			sumOfWaitingTimes += groupWaitingTime(*group, cookingTime);
			// printf("Czas czekania dla połączonej grupy (numMembers: %d, sumOfDelays: %lld): %lld\n", group->numMembers, group->sumOfDelays, groupWaitingTime(*group, cookingTime));
			scalarSum += groupScalarSum(*group);
			
			if (group->next != nullptr) {
				// printf("Grupa: %d zacznie interferować przy długości pieczenia: %lld\n", group->id, whenInterfereWithNext(*group));
				interferenceQueue.push(std::make_pair(-whenInterfereWithNext(*group), group));
			}
		}
		res.push_back(std::make_pair(queryId, sumOfWaitingTimes));
		prevCookingTime = cookingTimes[i].first;
	}

	std::sort(std::begin(res), std::end(res));
	for (unsigned i = 0; i < res.size(); ++i) {
		printf("%lld\n", res[i].second);
	}
}