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
#include <iostream>
#include <assert.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	size_t n, m;
	cin >> n >> m;

	assert(1 <= n);
	assert(n <= 200000);
	assert(1 <= m);
	assert(m <= 200000);

	struct Group {
		uint64_t t;
		uint32_t n;
		uint32_t prev;
		bool present;
	};
	vector<Group> G;
	G.push_back({0, 0, 0, true});
	for (size_t i = 0; i < n; i++) {
		uint64_t t;
		cin >> t;
		assert(t <= 1000000000000LL);
		assert(G.back().t <= t);
		if (G.back().t == t) {
			G.back().n++;
		} else {
			G.push_back({t, 0, uint32_t(G.size())-1, true});
		}
	}

	vector<uint32_t> O(m);
	for (size_t i = 0; i < m; i++) {
		int32_t d;
		cin >> d;
		assert(1 <= d);
		assert(d <= 1000000);
		O[i] = d;
	}
	vector<uint32_t> Od(m); // ovens by time
	for (uint32_t i = 0; i < m; i++) Od[i] = i;
	sort(Od.begin(), Od.end(), [&O](uint32_t a, uint32_t b) { return O[a] < O[b]; });

	vector<uint64_t> R(m);

	uint64_t W = 0;
	uint32_t D = 0;
	uint64_t w = 0;
	for (auto g: G) w += uint64_t(g.n+1) * g.n / 2;

	vector<uint32_t> P(uint32_t(G.size())-1);
	for (uint32_t i = 0; i < P.size(); i++) {
		P[i] = i + 1;
	}

	for (uint32_t i = 0; i < m; i++) {
		uint32_t d = O[Od[i]];
		uint32_t dd = d - D;
		vector<Group> NG;
		W += w * dd;
		for (uint32_t j = 0; j < P.size(); j++) {
			auto &g = G[P[j]];
			assert(g.present);
			uint32_t k = g.prev;
			while (!G[k].present) {
				uint32_t nk = G[k].prev;
				assert(nk != k);
				k = nk;
			}
			g.prev = k;
			auto &b = G[k];
			uint64_t le = b.t + uint64_t(b.n+1) * d;
			if (le > g.t) {
				uint64_t dW = le - g.t;
				W += (g.n+1) * dW;
				g.t += dW;
				w -= uint64_t(g.n+1) * g.n / 2;
				w -= uint64_t(b.n+1) * b.n / 2;
				b.n += g.n+1;
				w += uint64_t(b.n+1) * b.n / 2;

				g.present = false;
				P.erase(P.begin() + j);
				j--;
			}
		}
		R[Od[i]] = W;
		D = d;
	}

	for (auto r: R) cout << r << endl;
	return 0;
}