Submission #1231249

#TimeUsernameProblemLanguageResultExecution timeMemory
1231249alexander707070Text editor (CEOI24_editor)C++20
100 / 100
2480 ms114440 KiB
#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;

const long long inf=1e15;

struct Segment_Tree{
    long long tree[4*MAXN];
    long long lazy[4*MAXN];

    void psh(int v){
        if(lazy[v]==0)return;

        tree[2*v]+=lazy[v];
        tree[2*v+1]+=lazy[v];

        lazy[2*v]+=lazy[v];
        lazy[2*v+1]+=lazy[v];

        lazy[v]=0;
    }
    
    void update(int v,int l,int r,int ll,int rr,long long val){
        if(ll>rr)return;
        if(l==ll and r==rr){
            tree[v]+=val;
            lazy[v]+=val;
        }else{
            int tt=(l+r)/2;
            psh(v);

            update(2*v,l,tt,ll,min(tt,rr),val);
            update(2*v+1,tt+1,r,max(tt+1,ll),rr,val);

            tree[v]=min(tree[2*v],tree[2*v+1]);
        }
    }

    long long query(int v,int l,int r,int ll,int rr){
        if(ll>rr)return inf;

        if(l==ll and r==rr)return tree[v];

        int tt=(l+r)/2;
        psh(v);

        return min( query(2*v,l,tt,ll,min(tt,rr)) , query(2*v+1,tt+1,r,max(tt+1,ll),rr) );
    }

}seg,seg2,mins;

int n;
int srow,scol,erow,ecol;
int h[MAXN];
long long ans;

long long c[MAXN],d[MAXN];

long long go_straight(int r1,int c1,int r2,int c2){
    if(r1<1 or r1>n)return inf;
    if(r2<1 or r2>n)return inf;

    return abs(r1-r2) + abs( min(c1+0LL,mins.query(1,1,n,min(r1,r2),max(r1,r2)) ) - c2);
}

int main(){

    cin>>n;

    cin>>srow>>scol;
    cin>>erow>>ecol;

    for(int i=1;i<=n;i++){
        cin>>h[i];
        h[i]++;

        mins.update(1,1,n,i,i,h[i]);
    }

    ans=go_straight(srow,scol,erow,ecol);

    for(int i=1;i<=n;i++){
        if(i>1)ans=min(ans , go_straight(srow,scol,i,1) + 1 + go_straight(i-1,h[i-1],erow,ecol) );
        if(i<n)ans=min(ans , go_straight(srow,scol,i,h[i]) + 1 + go_straight(i+1,1,erow,ecol) );

        ans=min(ans , go_straight(srow,scol,i,h[i]) + go_straight(i,h[i],erow,ecol) );
    }

    for(int i=1;i<=n;i++){
        c[i]=go_straight(srow,scol,i,h[i]) + h[i];
        d[i]=go_straight(i-1,h[i-1],erow,ecol);

        seg.update(1,1,n,i,i,d[i]+i);
    }

    for(int i=1;i<=n;i++){
        seg.update(1,1,n,i,n,-1);
        seg.update(1,1,n,1,i-1,1);

        ans=min(ans,seg.tree[1]+c[i]);
    }

    for(int i=1;i<=n;i++){
        c[i]=go_straight(srow,scol,i,h[i])+2;
        d[i]=go_straight(i,h[i],erow,ecol);

        if(i<n)seg2.update(1,1,n-1,i,i,d[i]+i);
    }

    for(int i=1;i<=n;i++){
        seg2.update(1,1,n-1,i,n-1,-1);
        seg2.update(1,1,n-1,1,i-1,1);

        ans=min(ans,seg2.tree[1]+c[i]);
    }


    cout<<ans<<"\n";
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...