제출 #1265110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265110		kustov_vadim_533	Snowball (JOI21_ho_t2)	C++20	100 / 100	62 ms	9812 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define len(v) (int)((v).size())

const ll inf = 1e18;

inline void solve(){
	int n, q;
	cin >> n >> q;

	vector<ll> a(n), b(q);
	for (int i = 0; i < n; ++i){
		cin >> a[i];
	}
	for (int i = 0; i < q; ++i){
		cin >> b[i];
	}

	vector<ll> lf(q + 1, 0), rt(q + 1, 0);
	ll d = 0;
	for (int i = 0; i < q; ++i){
		d += b[i];
		lf[i + 1] = max(lf[i], -d);
		rt[i + 1] = max(rt[i], d);
	}

	vector<ll> ans(n, 0);
	for (int i = -1; i < n; ++i){
		ll d = inf;
		if (i >= 0 && i + 1 < n){
			d = a[i + 1] - a[i];
		}

		int li = 0, ri = q;
		while (ri - li > 1){
			int mi = (li + ri) / 2;

			if (lf[mi] + rt[mi] > d){
				ri = mi;
			}
			else{
				li = mi;
			}
		}

		ll x = min(lf[ri], d - rt[li]);
		ll y = min(rt[ri], d - lf[li]);

		if (i >= 0) ans[i] += y;
		if (i + 1 < n) ans[i + 1] += x;
	}

	for (int i = 0; i < n; ++i){
		cout << ans[i] << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(60);

	int t = 1;
//	cin >> t;

	while (t--) {
		solve();
	}
}

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