Submission #1095723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095723		zaza	Snowball (JOI21_ho_t2)	C++14	0 / 100	1 ms	600 KiB

Main

#include <bits/stdc++.h>

using namespace std;

long long a[200005], w[200005];

long long mini[200005], maxi[200005];

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, q;
	
	cin >> n >> q;
	
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	
	w[0] = 0;
	mini[0] = 2e18;
	maxi[0] = -2e18;
	
	for (int i = 1; i <= q; ++i) {
		cin >> w[i];
		w[i] += w[i - 1];
		mini[i] = min(mini[i - 1], w[i]);
		maxi[i] = max(maxi[i - 1], w[i]);
	}
	
	for (int i = 1; i <= n; ++i) {
		
		long long L, R;
		
		if (i == 1) {
			
			L = min(a[i], a[i] + mini[q]);
			
		} else {
			
			int l = 1, r = q;
			
			while (l <= r) {
				int mid = (l + r) / 2;
				if (min(a[i], a[i] + mini[mid]) <= max(a[i - 1], a[i - 1] + maxi[mid])) {
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			
			if (l > q) {
				L = min(a[i], a[i] + mini[q]);
			} else {
				L = max(a[i - 1], a[i - 1] + maxi[l]);
				if (l > 1) {
					L = min(L, min(a[i], a[i] + mini[l - 1]));
				}
			}
			//cout << "i = " << i << " i_l = " << l << '\n';
		}
		
		if (i == n) {
			
			R = max(a[i], a[i] + maxi[q]);
			
		} else {
			
			int l = 1, r = q;
			
			while (l <= r) {
				int mid = (l + r) / 2;
				if (max(a[i], a[i] + maxi[mid]) >= min(a[i + 1], a[i + 1] + mini[mid])) {
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			
			if (l > q) {
				R = max(a[i], a[i] + maxi[q]);
			} else {
				R = min(a[i + 1], a[i + 1] + mini[l]);
				if (l > 1) {
					R = max(R, max(a[i], a[i] + maxi[l - 1]));
				}
			}
			
			//cout << "i = " << i << " i_r = " << l << '\n';
		}
		
	//	cout <<"L = " << L<<" R = "<<R<<'\n';
		
		cout << R - L << '\n';
	}
	
}

Compilation message (stderr)

Main.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main() {
      | ^~~~

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