Submission #1231236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231236		alexander707070	Text editor (CEOI24_editor)	C++20	45 / 100	12 ms	4564 KiB

Main

#include<bits/stdc++.h>
#define MAXN 1007
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]);
        }
    }

}seg;

int n;
int srow,scol,erow,ecol;
int h[MAXN];
int minh[MAXN][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,minh[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]++;
    }

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

        for(int f=i+1;f<=n;f++){
            minh[i][f]=min(h[f],minh[i][f-1]);
        }
    }

    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++){
        for(int f=1;f<=n;f++){
            ans=min(ans , go_straight(srow,scol,i,h[i]) + 1 + go_straight(i+1,1,f,1) + 1 + go_straight(f-1,h[f-1],erow,ecol) );
        }
    }

    cout<<ans<<"\n";
    
    return 0;
}

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