답안 #386829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386829 2021-04-07T12:28:25 Z nikatamliani Snowball (JOI21_ho_t2) C++14
100 / 100
179 ms 12268 KB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10;
ll n, m, x[N], maxp[N], minp[N];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> x[i];
	}
	ll p = 0; 
	for(int i = 1; i <= m; ++i) {
		ll offset; cin >> offset;
		p += offset;
		maxp[i] = max(maxp[i - 1], p);
		minp[i] = min(minp[i - 1], p);
	}
	const ll oo = 1e18;
	x[0] = -oo;
	x[n+1] = oo;
	auto crit_point = [&](ll dist) {
		ll l = 0, r = m, ans = m;
		while(r >= l) {
			ll middle = l + r >> 1;
			if(maxp[middle] >= dist + minp[middle]) {
				r = middle-1;
				ans = middle;
			} else {
				l = middle+1;
			}
		}
		return ans;		
	};
	auto maximum = [&](ll a, ll b) {
		return max(a, b);
	};
	auto minimum = [&](ll a, ll b) {
		return min(a, b);
	};
	auto f = [&](ll id, ll A, ll B, function<ll(ll, ll)> fun) {
		id = max(id, 0LL);
		id = min(id, m);
		return fun(maxp[id] + A, minp[id] + B);
	};
	for(int i = 1; i <= n; ++i) {
		ll point_lft = crit_point(x[i] - x[i-1]);
		ll point_rgh = crit_point(x[i+1] - x[i]);
		ll lft = oo, rgh = -oo;
		for(int off = -1; off <= 1; ++off) {
			lft = min(lft, f(point_lft+off, x[i-1], x[i], maximum));
			rgh = max(rgh, f(point_rgh+off, x[i], x[i+1], minimum));
		}
		cout << rgh - lft << ' ';
	}
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:25:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |    ll middle = l + r >> 1;
      |                ~~^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 3 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 3 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 31 ms 3436 KB Output is correct
21 Correct 28 ms 3436 KB Output is correct
22 Correct 35 ms 3436 KB Output is correct
23 Correct 26 ms 3564 KB Output is correct
24 Correct 36 ms 3820 KB Output is correct
25 Correct 148 ms 6636 KB Output is correct
26 Correct 146 ms 6636 KB Output is correct
27 Correct 143 ms 6508 KB Output is correct
28 Correct 144 ms 6380 KB Output is correct
29 Correct 141 ms 6252 KB Output is correct
30 Correct 135 ms 5996 KB Output is correct
31 Correct 88 ms 5484 KB Output is correct
32 Correct 82 ms 5612 KB Output is correct
33 Correct 16 ms 1004 KB Output is correct
34 Correct 147 ms 6636 KB Output is correct
35 Correct 150 ms 6508 KB Output is correct
36 Correct 144 ms 6636 KB Output is correct
37 Correct 146 ms 6508 KB Output is correct
38 Correct 152 ms 6544 KB Output is correct
39 Correct 179 ms 6508 KB Output is correct
40 Correct 109 ms 6380 KB Output is correct
41 Correct 34 ms 3436 KB Output is correct
42 Correct 80 ms 8556 KB Output is correct
43 Correct 102 ms 11936 KB Output is correct
44 Correct 35 ms 6124 KB Output is correct
45 Correct 89 ms 10092 KB Output is correct
46 Correct 116 ms 12012 KB Output is correct
47 Correct 107 ms 12268 KB Output is correct
48 Correct 105 ms 12268 KB Output is correct