Submission #747876

#	Time	Username	Problem	Language	Result	Execution time	Memory
747876		JellyTheOctopus	Snowball (JOI21_ho_t2)	C++17	100 / 100	106 ms	15544 KiB

Main

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

int N, Q;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N >> Q;
	vector<long long> pos(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> pos[i];
	}
	vector<long long> space;
	vector<long long> L;
	vector<long long> R;
	vector<bool> get; // true is left
	space.push_back(0);
	L.push_back(0);
	R.push_back(0);
	get.push_back(0);
	long long farLeft = 0;
	long long farRight = 0;
	long long curPos = 0;
	long long spaceCovered = 0;
	for (int i = 1; i <= Q; i++) {
		long long add;
		cin >> add;
		if (add == 0) continue;
		curPos += add;
		if (i == 1) {
			spaceCovered += abs(curPos);
			space.push_back(spaceCovered);
			if (curPos > 0) {
				farRight = curPos;
				L.push_back(L.back()+curPos);
				R.push_back(R.back());
				get.push_back(1);
			}
			else {
				farLeft = curPos;
				L.push_back(L.back());
				R.push_back(R.back()-curPos);
				get.push_back(0);
			}
			continue;
		}
		if (curPos > farRight) {
			spaceCovered += abs(farRight-curPos);
			space.push_back(spaceCovered);
			L.push_back(L.back()+abs(farRight-curPos));
			R.push_back(R.back());
			get.push_back(1);
			farRight = curPos;
		}
		if (curPos < farLeft) {
			spaceCovered += abs(farLeft-curPos);
			space.push_back(spaceCovered);
			L.push_back(L.back());
			R.push_back(R.back()+abs(farLeft-curPos));
			get.push_back(0);
			farLeft = curPos;
		}
	}
	vector<long long> ans(N+1);
	for (int i = 1; i < N; i++) {
		long long diff = abs(pos[i+1]-pos[i]);
		auto it = lower_bound(space.begin(), space.end(), diff);
		if (it == space.end()) {
			ans[i] += L.back();
			ans[i+1] += R.back();
			continue;
		}
		int j = (it-space.begin());
		if (get[j]) {
			ans[i] += diff-R[j];
			ans[i+1] += R[j];
		}
		else {
			ans[i] += L[j];
			ans[i+1] += diff-L[j];
		}
	}
	ans[1] += abs(farLeft);
	ans[N] += abs(farRight);
	for (int i = 1; i <= N; i++) {
		cout << ans[i] << "\n";
	}
}

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