Submission #1097682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097682		Alihan_8	Snowball (JOI21_ho_t2)	C++17	33 / 100	2554 ms	9044 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#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];
		
		cnt += Q[i];
		
		f[i][0] = min(f[i][0], cnt);
		f[i][1] = max(f[i][1], cnt);
	}
	
	sort(all(f), [&](auto &u, auto &v){
		return u[1] - u[0] < v[1] - v[0];
	});
	
	vector <i64> A(n + 1), B(n + 1);
	
	for ( int i = 1; i <= n; i++ ){
		A[i] = X[i] - X[i - 1];
		B[i] = X[i + 1] - X[i];
	}
	
	vector <i64> L(n + 1), R(n + 1);
	
	{ // L
		vector <int> p(n);
		iota(all(p), 1);
		
		sort(all(p), [&](int &u, int &v){
			return A[u] < A[v];
		});
		
		vector <i64> pf(q + 1, inf), sf(q + 2, inf);
		
		for ( int i = 0; i < q; i++ ) pf[i + 1] = min(pf[i], f[i][0]);
		for ( int i = q; i > 0; i-- ) sf[i] = min(sf[i + 1], f[i - 1][1]);
		
		int j = 0;
		
		for ( auto &i: p ){
			L[i] = A[i];
			
			for ( int j = 0; j < q; j++ ){
				L[i] = min(L[i], max(f[j][1], f[j][0] + A[i]));
			}
			
			while ( j < q && f[j][1] <= A[i] + f[j][0] ) j++;
			
			for ( int k = 0; k < q; k++ ){
				if ( k < j ) L[i] = min(L[i], f[k][0] + A[i]);
				else L[i] = min(L[i], f[k][1]);
			}
			
			//~ L[i] = min({L[i], pf[j] + A[i], sf[j + 1]});
		}
	}
	{ // R
		vector <int> p(n);
		iota(all(p), 1);
		
		sort(all(p), [&](int &u, int &v){
			return B[u] < B[v];
		});
		
		vector <i64> pf(q + 1, -inf), sf(q + 2, -inf);
		
		for ( int i = 0; i < q; i++ ) pf[i + 1] = max(pf[i], f[i][1]);
		for ( int i = q; i > 0; i-- ) sf[i] = max(sf[i + 1], f[i - 1][0]);
		
		int j = 0;
		
		for ( auto &i: p ){
			for ( int j = 0; j < q; j++ ){
				R[i] = max(R[i], min(f[j][0] + B[i], f[j][1]));
			}
			
			continue;
			
			while ( j < q && f[j][1] <= B[i] + f[j][0] ) j++;
			
			R[i] = max({R[i], pf[j], sf[j + 1] + B[i]});
		}
	}
	
	for ( int i = 1; i <= n; i++ ){
		cout << R[i] - L[i] + A[i] << endl;
	}
	
	cout << '\n';
}

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