Submission #1219236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219236		trimkus	Snowball (JOI21_ho_t2)	C++20	0 / 100	5 ms	328 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);
	for (auto& i : a) cin >> i;
	vector<ll> res(n);
	vector<ll> l(n), r(n);
	for (int i = 0; i < n; ++i) {
		l[i] = r[i] = a[i];
	}
	vector<ll> psMax(q, LLONG_MIN), psMin(q, LLONG_MAX);
	ll total = 0;
	for (int i = 0; i < q; ++i) {
		ll x;
		cin >> x;
		total += x;
		psMax[i] = max({0LL, psMax[i], total});
		psMin[i] = min({0LL, psMin[i], total});
		if (i) {
			psMax[i] = max(psMax[i], psMax[i - 1]);
			psMin[i] = min(psMin[i], psMin[i - 1]);
		}
	}
	//~ for (int i = 0; i < q; ++i) {
		//~ cout << "ps max = " << psMax[i] << " , ps min = " << psMin[i] << "\n";
	//~ }
	//~ for (int i = 0; i < q; ++i) {
		//~ cerr << a[0] << " " << a[0] + psMax[i] << " " << a[1] + psMin[i] << "\n";
	//~ }
	//~ cerr << "\n";
	//~ for (int i = 0; i < q; ++i) {
		//~ cerr << a[1] << " " << a[1] + psMin[i] << " " << a[0] + psMax[i] << "\n";
	//~ }
	//~ cerr << "\n";
	//~ for (int i = 0; i < q; ++i) {
		//~ cerr << a[n - 1] << " " << a[n - 1] + psMin[i] << " " << a[n - 2] + psMax[i] << "\n";
	//~ }
	//~ cerr << "\n";
	for (int i = 0; i < n - 1; ++i) {
		int left = 0, right = q - 1;
		int idx = q - 1;
		while (left <= right) {
			int mid = (left + right);
			if (a[i] + psMax[mid] <= a[i + 1] + psMin[mid]) {
				left = mid + 1;
				idx = mid;
			} else {
				right = mid - 1;
			}
		}
		while (idx < q && psMin[idx] == psMin[idx + 1]) idx += 1;
		ll till = min(a[i] + psMax[idx], a[i + 1] + psMin[idx]);
		ll add = max(0LL, till - a[i]);
		//~ cerr << i << ", max right = " << a[i] + psMax[idx] << " , min left = " << a[i + 1] + psMin[idx] << ", initial position = " << a[i] << " , added w = " << add << "\n";
		res[i] += add;
	}
	//~ cerr << "right -> left:\n";
	for (int i = n - 1; i > 0; --i) {
		int left = 0, right = q - 1;
		int idx = q - 1;
		while (left <= right) {
			int mid = (left + right);
			//~ cerr << a[i - 1] + psMax[mid] << " <=? " << a[i] + psMin[mid] << "\n";
			if (a[i - 1] + psMax[mid] <= a[i] + psMin[mid]) {
				left = mid + 1;
				idx = mid;
			} else {
				right = mid - 1;
			}
		}
		//~ cerr << idx << " -> ";
		while (idx < q && psMax[idx] == psMax[idx + 1]) idx += 1;
		//~ cerr << idx << "\n";
		ll till = max(a[i] + psMin[idx], a[i - 1] + psMax[idx]);
		ll add = max(0LL, a[i] - till);
		//~ cerr << i << ", min left = " << a[i] + psMin[idx] << " , max left = " << a[i - 1] + psMax[idx] << ", initial position = " << a[i] << " , added w = " << add << "\n";
		res[i] += add;
	}
	{
		ll till = a[0] + psMin[q - 1];
		ll add = max(0LL, a[0] - till);
		res[0] += add;
	}
	{
		ll till = a[n - 1] + psMax[q - 1];
		ll add = max(0LL, till - a[n - 1]);
		res[n - 1] += add;
	}
	for (auto& i : res) {
		cout << i << "\n";
	}
}

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