Submission #921435

#	Time	Username	Problem	Language	Result	Execution time	Memory
921435		TAhmed33	Snowball (JOI21_ho_t2)	C++98	100 / 100	99 ms	15444 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int MAXN = 2e5 + 25;
ll a[MAXN], n, q;
ll pref[MAXN], u[MAXN], mx[MAXN], mn[MAXN];
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= q; i++) {
		cin >> u[i]; u[i] += u[i - 1];
		mx[i] = max(u[i], mx[i - 1]);
		mn[i] = min(u[i], mn[i - 1]);
	}
	a[0] = -inf; a[n + 1] = inf;
	for (int i = 1; i <= n; i++) {
		ll l = 1, r = q, ans1 = 0;
		ll tl = a[i - 1], tr = a[i + 1];
		while (l <= r) {
			ll mid = (l + r) >> 1;
			if (tl + mx[mid] < a[i] + mn[mid]) {
				l = mid + 1; ans1 = mid;
			} else {
				r = mid - 1;
			}
		}
		l = 1, r = q; ll ans2 = 0;
		while (l <= r) {
			ll mid = (l + r) >> 1;
			if (a[i] + mx[mid] < tr + mn[mid]) {
				l = mid + 1; ans2 = mid;
			} else {
				r = mid - 1;
			}
		}
		ll weight = -mn[ans1] + mx[ans2];
		//cout << tl + mx[ans1] << " " << a[i] + mn[ans1] << ": " << a[i] + mx[ans2] << " " << tr + mn[ans2] << '\n';
		if (ans1 < q) {
			ll x = tl + mx[ans1], y = a[i] + mn[ans1];
			if (u[ans1 + 1] < 0) {
				weight += y - x;
			}
		}
		if (ans2 < q) {
			ll x = a[i] + mx[ans2], y = tr + mn[ans2];
			if (u[ans2 + 1] > 0) {
				weight += y - x;
			}
		}
		cout << weight << '\n';
	}
}

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