Submission #1193146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193146		Unforgettablepl	Text editor (CEOI24_editor)	C++20	100 / 100	614 ms	65204 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    int startL,startC,endL,endC;
    cin >> startL >> startC >> endL >> endC;
    vector<int> l(N+1);
    for(int i=1;i<=N;i++){
        cin >> l[i];
        l[i]++;
    }
    vector<int> minimas = l;
    for(int i=endL+1;i<=N;i++)minimas[i]=min(minimas[i],minimas[i-1]);
    for(int i=endL-1;i;i--)minimas[i]=min(minimas[i],minimas[i+1]);
    auto trivialDist = [&](int x,int y){
        return abs(x-endL)+abs(min(y,minimas[x])-endC);
    };
    vector<int> beforeLower(N+1,-1);
    {
        stack<pair<int,int>> s;
        s.emplace(-1,-1);
        for(int i=1;i<=N;i++){
            while(s.top().first>l[i])s.pop();
            beforeLower[i]=s.top().second;
            s.emplace(l[i],i);
        }
    }
    vector<int> beforeAfter(N+1,-1);
    {
        stack<pair<int,int>> s;
        s.emplace(-1,-1);
        for(int i=N;i;i--){
            while(s.top().first>l[i])s.pop();
            beforeAfter[i]=s.top().second;
            s.emplace(l[i],i);
        }
    }
    vector<int> starts(N+1);
    vector<int> ends(N+1);
    vector<bool> visitedStarts(N+1);
    vector<bool> visitedEnds(N+1);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    int ans = trivialDist(startL,startC);
    pq.emplace(startC-1,startL);
    pq.emplace(l[startL]-startC,-startL);
    for(int i=startL-1;i;i--){
        if(l[i]<startC){
            pq.emplace(startL-i,-i);
            break;
        }
    }
    for(int i=startL+1;i<=N;i++){
        if(l[i]<startC){
            pq.emplace(i-startL,-i);
            break;
        }
    }
    while(!pq.empty()){
        auto [dist,idx] = pq.top();pq.pop();
        int type = 0;
        if(idx<0){type=1;idx=-idx;}
        if(type){
            if(visitedEnds[idx])continue;
            visitedEnds[idx]=true;
            ans = min(ans,dist+trivialDist(idx,l[idx]));  
            if(!visitedStarts[idx]){
                pq.emplace(dist+l[idx]-1,idx);
            }
            if(idx!=N and !visitedStarts[idx+1]){
                pq.emplace(dist+1,idx+1);
            }
            if(beforeLower[idx]!=-1 and !visitedEnds[beforeLower[idx]]){
                pq.emplace(dist+abs(beforeLower[idx]-idx),-beforeLower[idx]);
            }
            if(beforeAfter[idx]!=-1 and !visitedEnds[beforeAfter[idx]]){
                pq.emplace(dist+abs(beforeAfter[idx]-idx),-beforeAfter[idx]);
            }
        } else {
            if(visitedStarts[idx])continue;
            visitedStarts[idx]=true;
            ans = min(ans,dist+trivialDist(idx,1));
            if(!visitedEnds[idx]){
                pq.emplace(dist+l[idx]-1,-idx);
            }
            if(idx!=1 and !visitedEnds[idx-1]){
                pq.emplace(dist+1,-(idx-1));
            }
            if(idx!=1 and !visitedStarts[idx-1]){
                pq.emplace(dist+1,idx-1);
            }
            if(idx!=N and !visitedStarts[idx+1]){
                pq.emplace(dist+1,idx+1);
            }
        }
    }
    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