oj.uz

답안 #1095725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1095725 2024-10-03T03:42:44 Z zaza Snowball (JOI21_ho_t2) C++14
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

#define int long long

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:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main() {
      | ^~~~

Subtask #1
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 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 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 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 1 ms 344 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 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 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 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 1 ms 344 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -