Submission #696663

#	Time	Username	Problem	Language	Result	Execution time	Memory
696663		yaufung	Snowball (JOI21_ho_t2)	C++17	100 / 100	122 ms	15360 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define LL long long

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<LL> a(n + 5), Q(q + 5), ans(n + 5);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= q; i++) {
		cin >> Q[i];
	}
	vector<LL> l(q + 5), r(q + 5);
	LL p = 0;
	l[0] = r[0] = 0;
	for (int i = 1; i <= q; i++) {
		p += Q[i];
		r[i] = max(r[i - 1], -p);
		l[i] = max(l[i - 1], p);
	}
	ans[1] += r[q];
	ans[n] += l[q];
	for (int i = 1; i < n; i++) {
		LL diff = a[i + 1] - a[i];
		int bot = 0, top = q, mid;
		while (bot <= top) {
			mid = (bot + top) / 2;
			if (l[mid] + r[mid] >= diff) {
				top = mid - 1;				
			}
			else bot = mid + 1;
		}
		ans[i] += l[top];
		ans[i + 1] += r[top];
		LL remain = diff - l[top] - r[top];
		if (top < q) {
			if (l[top + 1] > l[top]) ans[i] += remain;
			else ans[i + 1] += remain;
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}

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