Submission #1219242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219242		trimkus	Snowball (JOI21_ho_t2)	C++20	100 / 100	143 ms	8220 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


int main() {
	int n, q;
	cin >> n >> q;
	vector<ll> a(n + 2);
	a[0] = -(ll)1e18;
	a[n + 1] = (ll)1e18;
	vector<pair<ll, int>> gaps;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		gaps.push_back({a[i] - a[i - 1], i});
	}
	gaps.push_back({a[n + 1] - a[n], n + 1});
	sort(begin(gaps), end(gaps));
	vector<ll> res(n + 2);
	ll l = 0, r = 0, w = 0;
	int ptr = 0;
	for (int i = 0; i < q; ++i) {
		ll x;
		cin >> x;
		if (x >= 0) {
			w += x;
			r = max(r, w);
			while (ptr < (int)gaps.size() && gaps[ptr].first <= r + l) {
				int j = gaps[ptr].second;
				res[j] += l;
				res[j - 1] += gaps[ptr].first - l;
				ptr += 1;
			} 
		} else {
			w += x;
			l = max(l, -w);
			while (ptr < (int)gaps.size() && gaps[ptr].first <= r + l) {
				int j = gaps[ptr].second;
				res[j - 1] += r;
				res[j] += gaps[ptr].first - r;
				ptr += 1;
			}
		}
	}
	while (ptr < (int)gaps.size()) {
		int j = gaps[ptr].second;
		res[j - 1] += r;
		res[j] += l;
		ptr += 1;
	}
	for (int i = 1; i <= n; ++i) {
		cout << res[i] << "\n";
	}
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67