Submission #1040983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040983		Lucpp	Text editor (CEOI24_editor)	C++17	100 / 100	82 ms	47952 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)size(x)
#define all(x) (x).begin(), (x).end()

constexpr ll inf = 1e18;

ll pmin(ll &x, ll y){
	return x = min(x, y);
}

int main(){
	cin.tie(0)->sync_with_stdio(false);
	int n;
	cin >> n;
	int sl, el; ll sc, ec;
	cin >> sl >> sc >> el >> ec;
	sl--, sc--, el--, ec--;
	vector<ll> a(n);
	for(ll& e : a) cin >> e;

	auto sweep = [&](vector<ll>& v){
		ll best = inf;
		for(int i = 0; i < n; i++){
			pmin(best, v[i] - i);
			pmin(v[i], best + i);
		}
		best = inf;
		for(int i = n-1; i >= 0; i--){
			pmin(best, v[i]+i);
			pmin(v[i], best-i);
		}
	};

	auto rangeMin = [&](int startInd, ll startCol){
		vector<ll> mi(n, inf);
		ll cur = startCol;
		for(int i = startInd; i < n; i++) mi[i] = pmin(cur, a[i]);
		cur = startCol;
		for(int i = startInd; i >= 0; i--) mi[i] = pmin(cur, a[i]);
		return mi;
	};

	vector<ll> smi = rangeMin(sl, sc), emi = rangeMin(el, inf);

	ll ans = inf;
	if(sc <= ec){
		pmin(ans, abs(sl - el) + abs(ec - smi[el]));
	}
	else{
		for(int i = 0; i < n; i++){
			pmin(ans, abs(sl - i) + abs(el - i) + abs(ec - min(smi[i], smi[el])));
		}
	}
	vector<ll> x(n, inf), y(n, inf);
	for(int i = 0; i < n; i++){
		if(i < n-1) pmin(x[i+1], a[i] - smi[i] + 1 + abs(sl-i));
		pmin(x[i], smi[i] + abs(sl-i));
	}
	sweep(x);
	for(int i = 0; i < n; i++){
		if(i < n-1) pmin(y[i+1], abs(ec - emi[i]) + 1 + abs(el-i));
		pmin(y[i], ec + abs(el-i));
	}
	sweep(y);
	for(int i = 0; i < n; i++){
		pmin(ans, x[i] + y[i]);
	}
	cout << ans << "\n";
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 26 / 26
• Subtask 4: 11 / 11
• Subtask 5: 44 / 44