제출 #1310802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310802		samarthkulkarni	Snowball (JOI21_ho_t2)	C++20	0 / 100	1 ms	332 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]);
	}

	// for (int i = 0; i < q; i++) {
	// 	cout << mn[i] << " " << mx[i] << endl;
	// }

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


	auto right = [&](int i, ll x) {
		int j = i+1;

		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[j] + mn[mid]) return true;
				r = mid-1;
			}
		}
		return false;
	};

	auto left = [&](int i, ll x) {
		int j = i-1;
		int l = 0, r = q-1;

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

		return false;

	};


	
	for (int i = 2; i < n; i++) {


		int l = 0, r = min(a[i+1]-a[i], mx[q-1])+10;
		ll t = 0;

		while (l <= r) {
			ll mid = (l + r)/2;

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



		res[i] += t;
		t = 0;
		l = 0, r = min(a[i] - a[i-1], abs(mn[q-1]))+10;
		while (l <= r) {
			ll mid = (l + r)/2;
			if (left(i, mid)) {
				t = mid;
				l = mid+1;
			} else r = mid-1;
		}

		res[i] += t;

	}


	ll l = 0, r = min(a[2]-a[1], mx[q-1])+10;
	ll t = 0;
	while (l <= r) {
		ll mid = (l + r)/2;
		if (right(1, mid)) {
			t = mid;
			l = mid+1;
		} else r = mid-1;
	}
	res[1] += abs(mn[q-1]) + t;
	t = 0;
	l = 0, r = min(a[n] - a[n-1], -mn[q-1])+10;
	while (l <= r){
		ll mid = (l + r)/2;

		if (left(n, mid)) {
			t = mid;
			l = mid+1;
		} else r = mid-1;
	}
	res[n] += mx[q-1] + t;
	for (int i = 1; i <= n; i++) cout << res[i] << endl;





}

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