Submission #386823

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
386823	2021-04-07T12:12:10 Z	nikatamliani	Snowball (JOI21_ho_t2)	C++14	33 / 100	2500 ms	5740 KB

Main

#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 = 1e15;
	x[0] = -oo;
	x[n+1] = oo;
	auto crit_point = [&](ll dist) {
		ll l = 0, r = m, ans = -1;
		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 lft = oo, rgh = -oo;
		for(int j = 0; j <= m; ++j) {
			lft = min(lft, f(j, x[i-1], x[i], maximum));
			rgh = max(rgh, f(j, x[i], x[i+1], minimum));
		}
//		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] - x[i-1], maximum));
//			rgh = max(rgh, f(point_rgh+off, x[i+1] - x[i], minimum));
//		}
//		cout << lft << ' ' << rgh << '\n';
		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;
      |                ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:22:7: warning: variable 'crit_point' set but not used [-Wunused-but-set-variable]
   22 |  auto crit_point = [&](ll dist) {
      |       ^~~~~~~~~~

Subtask #1

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	2 ms	364 KB	Output is correct
3	Correct	5 ms	364 KB	Output is correct
4	Correct	38 ms	492 KB	Output is correct
5	Correct	38 ms	492 KB	Output is correct
6	Correct	38 ms	492 KB	Output is correct
7	Correct	39 ms	492 KB	Output is correct
8	Correct	43 ms	492 KB	Output is correct
9	Correct	38 ms	492 KB	Output is correct
10	Correct	46 ms	492 KB	Output is correct
11	Correct	42 ms	492 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	2 ms	364 KB	Output is correct
15	Correct	40 ms	492 KB	Output is correct
16	Correct	38 ms	492 KB	Output is correct
17	Correct	40 ms	492 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	39 ms	492 KB	Output is correct

Subtask #2

0 / 67.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	2 ms	364 KB	Output is correct
3	Correct	5 ms	364 KB	Output is correct
4	Correct	38 ms	492 KB	Output is correct
5	Correct	38 ms	492 KB	Output is correct
6	Correct	38 ms	492 KB	Output is correct
7	Correct	39 ms	492 KB	Output is correct
8	Correct	43 ms	492 KB	Output is correct
9	Correct	38 ms	492 KB	Output is correct
10	Correct	46 ms	492 KB	Output is correct
11	Correct	42 ms	492 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	2 ms	364 KB	Output is correct
15	Correct	40 ms	492 KB	Output is correct
16	Correct	38 ms	492 KB	Output is correct
17	Correct	40 ms	492 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	39 ms	492 KB	Output is correct
20	Correct	36 ms	5740 KB	Output is correct
21	Correct	67 ms	5484 KB	Output is correct
22	Correct	392 ms	5356 KB	Output is correct
23	Execution timed out	2570 ms	5252 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-