제출 #1137573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137573		AbdullahIshfaq	Text editor (CEOI24_editor)	C++20	100 / 100	1658 ms	141804 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
const int N = 1000005;
void solve() {
	ll n, s1, s2, e1, e2;
    cin >> n;
    cin >> s1 >> s2 >> e1 >> e2;
    s1--;
	s2--;
	e1--;
	e2--;
    vector<ll> arr(n), left(n), right(n);
    for (int i = 0; i < n; i ++){
		cin >> arr[i];
	}
    vector<ll> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() and arr[st.back()] > arr[i]){
			st.pop_back();
		}
		if(st.empty()){
			left[i] = -1;
		}
		else{
			left[i] = st.back();
		}
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() and arr[st.back()] > arr[i]){
			st.pop_back();
		}
        if(st.empty()){
			right[i] = -1;
		}
		else{
			right[i] = st.back();
		}
        st.push_back(i);
    }
    ll ans = 1e18;
	ll mn1 = min(s1, e1), mn2 = max(s1, e1), mn = 1e9;
	for(int i = mn1; i <= mn2 ;i ++){
		mn = min(mn, arr[i]);
	}
	if(s1 == s2 or mn >= min(s2, e2)){
		ans = abs(s1 - e1) + abs(s2 - e2);
	}
	vector<vector<ll>> dist(n + 1, vector<ll> (2, 1e9));
    priority_queue<tuple<ll, ll, ll>> pq;
    auto put = [&](ll pp, ll tt, ll dd){
        if (dist[pp][tt] > dd) {
            dist[pp][tt] = dd;
            pq.push({-dd, pp, tt});
        }
    };
    put(s1, 0, s2);
	mn = 1e9;
    for(int i = s1; i >= 0; i--){
        mn = min(mn, arr[i]);
        put(i, 1, abs(i - s1) + max(0ll, arr[i] - s2));
        if(mn < s2){
			break;
		}
    }
	mn = 1e9;
    for(int i = s1; i < n; i++){
        mn = min(mn, arr[i]);
        put(i, 1, abs(i - s1) + max(0ll, arr[i] - s2));
        if(mn < s2){
			break;
		}
    }
    while(!pq.empty()){
        auto [dis, pos, typ] = pq.top();
        pq.pop();
        dis = -dis;
        if(dist[pos][typ] != dis){
			continue;
		}
        if(typ == 0){
            if(pos >= 1){
                put(pos - 1, 0, dis + 1);
                put(pos - 1, 1, dis + 1);
            }
            if(pos <= n - 2){
				put(pos + 1, 0, dis + 1);
			}
            put(pos, 1, dis + arr[pos]);
        } 
		else{
            put(pos, 0, dis + arr[pos]);
            if(pos <= n - 2){
				put(pos + 1, 0, dis + 1);
			}
            for(int x = pos - 1; x >= 0; x = left[x]){
                put(x, 1, dis + pos - x + max(0ll, arr[x] - arr[pos]));
                if(arr[x] <= arr[pos]){
					break;
				}
            }
            for(int x = pos + 1; x < n; x = right[x]){
                put(x, 1, dis + x - pos + max(0ll, arr[x] - arr[pos]));
                if(arr[x] <= arr[pos]){
					break;
				}
            }
        }
    }
    for(int i = 0; i < n; i++){
        ans = min(ans, dist[i][0] + e2 + abs(e1 - i));
    }
	mn = 1e9;
    for(int i = e1; i >= 0; i--){
        mn = min(mn, arr[i]);
        ans = min(ans, dist[i][1] + abs(arr[i] - e2) + abs(e1 - i));
        if(mn < e2){
			break;
		}
    }
	mn = 1e9;
    for(int i = e1; i < n; i++) {
        mn = min(mn, arr[i]);
        ans = min(ans, dist[i][1] + abs(arr[i] - e2) + abs(e1 - i));
        if(mn < e2){
			break;
		}
	}
    cout << ans << '\n';
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for (int i = 1; i <= tests; i++) {
		solve();
	}
}

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