Submission #768212

#	Time	Username	Problem	Language	Result	Execution time	Memory
768212		NK_	Snowball (JOI21_ho_t2)	C++17	100 / 100	269 ms	15404 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using ll = long long;
template<class T> using V = vector<T>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, Q; cin >> N >> Q;
	V<ll> A(N); for(auto& x : A) cin >> x;

	V<ll> MN(Q + 1, 0), MX(Q + 1, 0);
	ll cur = 0;
	for(int i = 1; i <= Q; i++) {
		ll x; cin >> x; cur += x;
		MN[i] = min(MN[i-1], cur);
		MX[i] = max(MX[i-1], cur);
		assert(MN[i] == MN[i-1] || MX[i] == MX[i-1]);
	}	

	V<ll> L(N), R(N);

	L[0] = MN.back() + A[0];
	R[N-1] = MX.back() + A[N-1];

	for(int i = 0; i < N-1; i++) {
		int lo = 0, hi = Q;
		while(lo < hi) {
			int mid = (lo + hi) / 2;

			ll l = MX[mid] + A[i], r = MN[mid] + A[i+1];
			if (l > r) hi = mid;
			else lo = mid + 1; 
		}

		int P = lo; assert(lo != 0);
		// cout << i << " " << P << endl;
		if (MX[P - 1] == MX[P]) {
			R[i] = MX[P] + A[i];
			L[i+1] = max(R[i], MN[P] + A[i+1]);
		} else {
			L[i+1] = MN[P] + A[i+1];
			R[i] = min(L[i+1], MX[P] + A[i]);
		}	
	}

	// for(int i = 0; i < N; i++) {
	// 	cout << L[i] << " | " << R[i] << endl;
	// }	

	for(int i = 0; i < N; i++) cout << R[i] - L[i] << endl;

    return 0;
}

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