Submission #1101244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101244		Mighilon	Text editor (CEOI24_editor)	C++17	100 / 100	286 ms	18788 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int mxN=1e7+1;
 
void solve(){
    int n;
    cin>>n;
    int si,sj,ei,ej;
    cin>>si>>sj>>ei>>ej;
    si--,sj--,ei--,ej--;
    vi a(n);
    F0R(i,n)cin>>a[i];
    int res=2e9;
    {
		int mn=sj;
		FOR(i,min(si,ei),max(ei,si)+1)
			mn=min(mn,a[i]);
		int tmp=mn;
		FOR(i,si,n){
			tmp=min(tmp,a[i]);
			res=min(res,abs(tmp-ej)+abs(si-i)+abs(i-ei));
		}
		tmp=mn;
		FORd(i,0,si){
			tmp=min(tmp,a[i]);
			res=min(res,abs(tmp-ej)+abs(si-i)+abs(i-ei));
		}
    }
	dbg(res);
    vi mn(n, 1e9);
    int tmp=sj;
    FOR(i,si,n){
        if(i>si)
            mn[i]=min({mn[i],mn[i-1]+1,i-si+a[i-1]-tmp});
        tmp=min(tmp,a[i]);
        mn[i]=min(mn[i],i-si+tmp);
    }

	dbg(mn)
    tmp=sj;
    FORd(i,0,si){
        tmp=min(tmp,a[i]);
        if(i+1<n){
            mn[i+1]=min(mn[i+1],a[i]-tmp+si-i+1);
            mn[i]=min(mn[i],mn[i+1]+1);
        }
		mn[i]=min(mn[i],tmp+si-i);
    }
	dbg(mn)
    tmp=1e9;
    F0R(i,n){
        mn[i]=min(mn[i],tmp);
        tmp=min(tmp,mn[i]);
        tmp++;
    }
    tmp=1e9;
    F0Rd(i,n){
        mn[i]=min(mn[i],tmp);
        tmp=min(tmp,mn[i]);
        tmp++;
    }
	dbg(mn);
    res=min(res,mn[ei]+ej);
	dbg(res);
    tmp=1e9;
    FOR(i,ei,n-1){
        tmp=min(tmp,a[i]);
        res=min(res,mn[i+1]+abs(ej-tmp)+i-ei+1);
        //cout<<i<<" "<<mn[i+1]<<" "<<ej-tmp<<" "<<i-ei<<" "<<endl;
    }
	dbg(res);
    tmp=a[ei];
    FORd(i,1,ei+1){
        tmp=min(tmp,a[i-1]);
        res=min(res,mn[i]+abs(ej-tmp)+ei-i+2);
    }
    cout<<res<<endl;
}
 
int main() {
    int t=1;
    //cin>>t;
    while(t--)
    solve();
    return 0;
}

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