Submission #529511

#TimeUsernameProblemLanguageResultExecution timeMemory
529511abc864197532Snowball (JOI21_ho_t2)C++17
100 / 100
314 ms11436 KiB
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
	cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
	for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(x...) abc("[" + string(#x) + "]", x)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(x...) void(0)
#define owo ios::sync_with_stdio(false), cin.tie(0)
#endif
const int N = 200000;

int main () {
	owo;
	int n, q;
	cin >> n >> q;
	vector <lli> a(n);
	lli move_mx = 0, move_mn = 0, now = 0, x;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	vector <lli> ans(n);
	vector <int> p(n);
	iota(all(p), 0);
	sort(p.begin(), p.begin() + n - 1, [&](int i, int j) {
		return a[i + 1] - a[i] < a[j + 1] - a[j];
	});
	int j = 0;
	for (int i = 0; i < q; ++i) {
		cin >> x, now += x;
		move_mx = max(move_mx, now);
		move_mn = min(move_mn, now);
		while (j < n - 1 && a[p[j] + 1] - a[p[j]] <= move_mx - move_mn) {
			lli d = a[p[j] + 1] - a[p[j]];
			if (x < 0) {
				ans[p[j]] += move_mx, ans[p[j] + 1] += d - move_mx;
			} else {
				ans[p[j] + 1] += -move_mn, ans[p[j]] += d + move_mn;
			}
			j++;
		}
	}
	while (j < n - 1) {
		ans[p[j]] += move_mx, ans[p[j] + 1] += -move_mn;
		j++;
	}
	ans[0] += -move_mn, ans[n - 1] += move_mx;
	for (lli i : ans)
		cout << i << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...