제출 #1310846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310846		samarthkulkarni	Snowball (JOI21_ho_t2)	C++20	100 / 100	672 ms	9972 KiB

Main

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

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


const int N = 2e5+10;
ll a[N];
ll qw[N];
ll res[N];

ll mx[N], mn[N];

void solution() {
	ll n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 0; i < q; i++) cin >> qw[i];



	mx[0] = max(0ll, qw[0]);
	mn[0] = min(0ll, qw[0]);
	
	for (int i = 1; i < q; i++) {
		qw[i] += qw[i-1];
		mx[i] = max(mx[i-1], qw[i]);
		mn[i] = min(mn[i-1], qw[i]);
	}


	if (n == 1) {
		cout << abs(mn[q-1]) + mx[q-1] << endl;
		return;
	}


	auto right = [&](int i, ll x) {
		if (x > mx[q-1]) return false;

		int l = 0, r = q-1;
		while (l <= r) {
			int mid = (l + r)/2;

			if (mx[mid] < x) l = mid+1;
			else {
				if (a[i] + x <= a[i+1] + mn[mid]) return true;
				r = mid-1;
			}
		}

		return false;
	};

	auto left = [&](int i, ll x) {
		if (x > abs(mn[q-1])) return false;
		int l = 0, r = q-1;
		while (l <= r) {
			int mid = (l + r)/2;

			if (-mn[mid] < x) l = mid+1;
			else {
				if (a[i]-x >= a[i-1] + mx[mid]) return true;
				r = mid-1;
			}
		}

		return false;
	};


	auto calculate = [&](int i, bool t) {
		ll l = 0, r = 1e13;
		ll w = 0;
		while (l <= r) {
			ll mid = (l + r)/2;

			if (t) {
				if (right(i, mid)) {
					w = mid;
					l = mid+1;
				} else r = mid-1;
			} else {
				if (left(i, mid)) {
					w = mid;
					l = mid+1;
				} else r = mid-1;
			}
		}

		return w;
	};	


	for (int i = 2; i < n; i++) {
		res[i] = calculate(i, 1) + calculate(i, 0);
	}

	res[1] = calculate(1, 1) -mn[q-1];
	res[n] = calculate(n, 0) + mx[q-1];

	for (int i = 1; i <= n; i++) cout << res[i] << endl;

}

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