Submission #1282276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282276		kaiboy	Snowball (JOI21_ho_t2)	C++20	100 / 100	62 ms	9976 KiB

Main

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 200000;
const int M = 200000;

long long xx[N], dd[M], ll[M], rr[M], ss[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> xx[i];
	for (int h = 0; h < m; h++)
		cin >> dd[h];
	long long x = 0, l = 0, r = 0;
	for (int h = 0; h < m; h++) {
		x += dd[h];
		ll[h] = l = min(l, x);
		rr[h] = r = max(r, x);
	}
	ss[0] -= ll[m - 1];
	ss[n - 1] += rr[m - 1];
	for (int i = 0; i + 1 < n; i++) {
		long long d = xx[i + 1] - xx[i];
		int lower = -1, upper = m;
		while (upper - lower > 1) {
			int h = lower + upper >> 1;
			if (rr[h] - ll[h] <= d)
				lower = h;
			else
				upper = h;
		}
		int h = lower;
		if (h >= 0) {
			ss[i] += rr[h];
			ss[i + 1] -= ll[h];
		}
		if (h + 1 < m)
			ss[i + (dd[h + 1] < 0)] += d - (rr[h] - ll[h]);
	}
	for (int i = 0; i < n; i++)
		cout << ss[i] << '\n';
	return 0;
}

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