제출 #1204278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204278		NK_	Text editor (CEOI24_editor)	C++20	100 / 100	1185 ms	157020 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

#define f first
#define s second
#define mp make_pair

using ll = long long;
using pl = pair<ll, ll>;
template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
using vi = V<int>;
using vl = V<ll>;
using vpl = V<pl>;

const ll INFL = 1e18;
// void solve(int N, int r, int c, int R, int C, vi A) {

// 	V<vl> dst(N);
// 	for(int i = 0; i < N; i++) dst[i] = vl(A[i], INFL);
// 	pq<array<ll, 3>> q; q.push({dst[r][c] = 0, r, c});

// 	while(sz(q)) {
// 		auto [d, r, c] = q.top();

// 		if (dst[r][c] != d) continue;

// 		// left
// 		if (c + 1 < A[r]


// 	}



// }


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	int r, c; cin >> r >> c; --r, --c;
	int R, C; cin >> R >> C; --R, --C;

	vl A(N); for(auto& x : A) cin >> x;


	vi nxt(N), prv(N);
	for(int t = 0; t < 2; t++) {
		vi stk = {-1};
		for(int i = 0; i < N; i++) {
			while(stk.back() != -1 && A[stk.back()] > A[i]) stk.pop_back();
			prv[i] = stk.back();
			stk.push_back(i);
		}

		prv.swap(nxt);
		reverse(begin(A), end(A));
	}

	reverse(begin(nxt), end(nxt));
	for(int i = 0; i < N; i++) nxt[i] = N - 1 - nxt[i];

	// for(int i = 0; i < N; i++) cout << prv[i] << " " << nxt[i] << endl;

	V<vl> dst(N, vl(2, INFL)); // distance to 0 - start of line, 1 - end of line

	{ 
		ll at = c;
		for(int i = r; i < N; i++) {
			dst[i][0] = min(dst[i][0], abs(r - i) + at);
			dst[i][1] = min(dst[i][1], abs(r - i) + A[i] - at);
			if (i + 1 < N) at = min(A[i + 1], at);
		}
	}

	{ 
		ll at = c;
		for(int i = r; i >= 0; i--) {
			dst[i][0] = min(dst[i][0], abs(r - i) + at);
			dst[i][1] = min(dst[i][1], abs(r - i) + A[i] - at);
			if (i - 1 >= 0) at = min(A[i - 1], at);
		}
	}

	pq<pl> q; for(int i = 0; i < N; i++) {  
		q.push(mp(dst[i][0], i));
		q.push(mp(dst[i][1], i + N));
	}

	V<vi> vis(N, vi(2));
	while(sz(q)) {
		auto [d, u] = q.top(); q.pop();

		int t = 0; if (u >= N) u -= N, t = 1;

		if (vis[u][t]) continue;
		vis[u][t] = 1;

		// cout << u << " " << t << " -> " << dst[u][t] << endl;


		if (t == 0) { // start of line
			if (u - 1 >= 0 && dst[u - 1][1] > dst[u][0] + 1) { // start to end of line (left)
				dst[u - 1][1] = dst[u][0] + 1;
				q.push(mp(dst[u - 1][1], u - 1 + N));
			}

			if (u - 1 >= 0 && dst[u - 1][0] > dst[u][0] + 1) { // start to start of line (up)
				dst[u - 1][0] = dst[u][0] + 1;
				q.push(mp(dst[u - 1][0], u - 1));
			}

			if (u + 1 < N && dst[u + 1][0] > dst[u][0] + 1) { // start to start of line (dwn)
				dst[u + 1][0] = dst[u][0] + 1;
				q.push(mp(dst[u + 1][0], u + 1));
			}

			if (dst[u][1] > dst[u][0] + A[u]) { // (right)
				dst[u][1] = dst[u][0] + A[u];
				q.push(mp(dst[u][1], u + N));
			}
		} else { // end of line
			if (u + 1 < N && dst[u + 1][0] > dst[u][1] + 1) { // end to start of line (right)
				dst[u + 1][0] = dst[u][1] + 1;
				q.push(mp(dst[u + 1][0], u + 1));
			}

			if (dst[u][0] > dst[u][1] + A[u]) { // (left)
				dst[u][0] = dst[u][1] + A[u];
				q.push(mp(dst[u][0], u));
			}

			if (u - 1 >= 0 && dst[u - 1][1] > dst[u][1] + abs(A[u] - A[u - 1]) + 1) { // (up)
				dst[u - 1][1] = dst[u][1] + abs(A[u] - A[u - 1]) + 1;
				q.push(mp(dst[u - 1][1], u - 1 + N));
			}

			if (u + 1 < N && dst[u + 1][1] > dst[u][1] + abs(A[u] - A[u + 1]) + 1) { // (dwn)
				dst[u + 1][1] = dst[u][1] + abs(A[u] - A[u + 1]) + 1; 
				q.push(mp(dst[u + 1][1], u + 1 + N));
			}

			if (prv[u] != -1 && dst[prv[u]][1] > dst[u][1] + abs(prv[u] - u)) { // (up)
				dst[prv[u]][1] = dst[u][1] + abs(prv[u] - u);
				q.push(mp(dst[prv[u]][1], prv[u] + N));
			}

			if (nxt[u] != N && dst[nxt[u]][1] > dst[u][1] + abs(nxt[u] - u)) { // (dwn)
				dst[nxt[u]][1] = dst[u][1] + abs(nxt[u] - u);
				q.push(mp(dst[nxt[u]][1], nxt[u] + N));
			}
		}
	}

	ll ans = INFL;
	
	ll at = c;
	for(int i = min(r, R); i <= max(r, R); i++) at = min(at, A[i]);
	ans = min(ans, abs(R - r) + abs(at - C));	

	// cout << ans << nl;
	
	{
		ll mn = A[R];
		for(int i = R; i >= 0; i--) {
			mn = min(A[i], mn);
			ans = min(ans, dst[i][1] + abs(i - R) + abs(mn - C));
			ans = min(ans, dst[i][0] + abs(i - R) + C);
			// cout << ans << nl;
		}
	}

	{
		ll mn = A[R];
		for(int i = R; i < N; i++) {
			mn = min(A[i], mn);
			ans = min(ans, dst[i][1] + abs(i - R) + abs(mn - C));
			ans = min(ans, dst[i][0] + abs(i - R) + C);
			// cout << ans << nl;
		}
	}

	cout << ans << nl;


	exit(0-0);
}

// Breathe In, Breathe Out

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