제출 #1134512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134512		ReLice	Text editor (CEOI24_editor)	C++20	0 / 100	1 ms	328 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}

const ll inf = 1e18;
const ll N = 1e6 + 8;

ll sp[N][20];

void solve() {
    ll i, j;

    ll n;
    cin>>n;

    ll x[2], y[2];
    for(i=0;i<2;i++) cin>>x[i]>>y[i];

    ll l[n + 1];
    l[0] = inf;

    for(i=1;i<=n;i++) cin>>l[i];

    ll mn = min(y[0], y[1]);

    for(i=min(x[0], x[1]);i<=max(x[0], x[1]);i++){
        mn = min(mn, l[i] + 1);
    }

    ll ans = y[0] - mn + y[1] - mn + abs(x[1] - x[0]);

    ll d[2][n + 1];

    for(i=0;i<2;i++){
        ll a = x[i], b = y[i];
        ll mn = inf;

        d[i][1] = b - 1 + a - 1;

        for(j=a - 1;j>0;j--){
            mn = min(mn, l[j] + 1);
            d[i][j + 1] = min(b - 1 + abs(j + 1 - a), max(0ll, mn - b) + 1 + abs(j - a));
        }

        mn = inf;

        for(j=a;j<n;j++){
            mn = min(mn, l[j] + 1);
            d[i][j + 1] = min(b - 1 + abs(j + 1 - a), max(0ll, mn - b) + 1 + abs(j - a));
        }

        multiset<ll> prev, nxt;

        for(j=2;j<=n;j++){
            nxt.ins(d[i][j] + j);
        }

        for(j=1;j<=n;j++){
            if(nxt.size()) d[i][j] = min(d[i][j], *nxt.begin() - j);
            if(prev.size()) d[i][j] = min(d[i][j], *prev.begin() + j);

            if(j < n) nxt.erase(nxt.find(d[i][j + 1] + j + 1));
            prev.ins(d[i][j] - j);
        }
    }

    for(i=1;i<=n;i++){
        ans = min(ans, d[0][i] + abs(x[1] - i) + y[1] - 1);
    }

    ll a = x[1], b = y[1];

    for(i=1;i<=n;i++) sp[i][0] = l[i] + 1;

    for(j=1;j<20;j++){
        for(i=1;i<=n;i++){
            sp[i][j] = min(sp[i][j - 1], sp[min(n, i + (1<<(j - 1)))][j - 1]);
        }
    }

    auto get_min = [&](ll l, ll r){
        ll lg = __lg(r - l);

        return min(sp[l][lg], sp[r - (1<<lg) + 1][lg]);
    };

    for(i=1;i<n;i++){
        ans = min(ans, d[0][i + 1] + 1 + abs(a - i) + abs(get_min(min(i, a), max(i, a)) - b));
    }

    cout<<ans<<endl;
}

signed main(){
    start();

    ll t = 1;
    //cin>>t;

    while(t--) solve();
}

/*


*/

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