Submission #386823

#	Time	Username	Problem	Language	Result	Execution time	Memory
386823		nikatamliani	Snowball (JOI21_ho_t2)	C++14	33 / 100	2570 ms	5740 KiB

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 (stderr)

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 / 33
• Subtask 2: 0 / 67