Submission #1097537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097537		Alihan_8	Snowball (JOI21_ho_t2)	C++17	33 / 100	2573 ms	7252 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ar array

using i64 = long long;

const i64 inf = 1e18;

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, q; cin >> n >> q;
	
	vector <i64> X(n + 2);
	
	for ( int i = 1; i <= n; i++ ){
		cin >> X[i];
	}
	
	X[0] = -inf, X[n + 1] = inf;
	
	vector <i64> Q(q);
	
	for ( auto &x: Q ) cin >> x;
	
	vector <ar<i64,2>> f(q);
	
	i64 cnt = 0;
	
	for ( int i = 0; i < q; i++ ){
		if ( i > 0 ) f[i] = f[i - 1];
		else f[i] = {inf, -inf};
		
		cnt += Q[i];
		
		f[i][0] = min(f[i][0], cnt);
		f[i][1] = max(f[i][1], cnt);
	}
	
	vector <i64> ans(n + 1);
	
	for ( int i = 1; i <= n; i++ ){
		i64 l = X[i], r = X[i];
		
		for ( int j = 0; j < q; j++ ){
			l = min(l, max(f[j][0] + X[i], f[j][1] + X[i - 1]));
			r = max(r, min(f[j][1] + X[i], f[j][0] + X[i + 1]));
		}
		
		l = max(l, X[i - 1]), r = min(r, X[i + 1]);
		
		ans[i] = r - l;
	}
	
	for ( int i = 1; i <= n; i++ ){
		cout << ans[i] << endl;
	}
	
	cout << '\n';
}

• Subtask 1: 33 / 33
• Subtask 2: 0 / 67