Submission #1095722

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1095722	2024-10-03T03:39:47 Z	vjudge1	Snowball (JOI21_ho_t2)	C++11	0 / 100	2 ms	604 KB

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

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

Subtask #1

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	528 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	2 ms	516 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Incorrect	0 ms	348 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 67.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	528 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	2 ms	516 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Incorrect	0 ms	348 KB	Output isn't correct
15	Halted	0 ms	0 KB	-