Submission #3615753

---

Source Code Expand

#include <bits/stdc++.h>

#ifdef __WIN32
#define LLFORMAT "I64"
#else
#define LLFORMAT "ll"
#endif

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	int n, s = 0, base = 0;
	cin >> n;
	--n;
	int foo, bar;
	cin >> foo >> bar;
	base = foo - bar;
	n -= 2;
	vector<int> a(n), suf_sum(n + 1, 0);
	vector<vector<pair<int, int> > > all(n);
	for (int i = 0; i < n; ++i) cin >> a[i], s += a[i];
	vector<int> rem(s);
	for (int t = 0, i = n - 1; ~i; --i) {
		suf_sum[i] = suf_sum[i + 1] + a[i];
		for (int j = 0; j < a[i]; ++j) rem[t + j] = i;
		t += a[i];
	}
	int m;
	cin >> m;
	vector<int> q(m), ans(m);
	for (int i = 0; i < m; ++i) {
		cin >> q[i];
		if(q[i] >= s) ans[i] = q[i] - s + base;
		else all[rem[q[i]]].push_back(make_pair(i, q[i] - suf_sum[rem[q[i]] + 1]));
	}
	deque<int> dp;
	for (int i = 0; i < n; ++i) {
		while(dp.size() <= a[i]) dp.push_back(dp.size() == 0 ? 0 : dp.back() + 1);
		for (int j = dp.size() - 1, end_j = j - a[i]; j > end_j; --j) dp.push_front(dp[dp.size() - j]);
		for (auto t: all[i]) ans[t.first] = dp[t.second] + base;
	}
	copy(ans.begin(), ans.end(), ostream_iterator<int>(cout, "\n"));
	return 0;
}

Submission Info

Judge Result