Submission #1177600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177600		alexdd	Text editor (CEOI24_editor)	C++20	100 / 100	608 ms	72616 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e17;
int n,slin,scol,elin,ecol;
int l[1000005],tole[1000005],tori[1000005];
int dist[1000005][2];
int solve()
{
    int rez=INF;
    bool bun=1;
    for(int i=min(slin,elin);i<=max(slin,elin);i++)
    {
        if(l[i] < min(scol,ecol))
            bun = 0;
    }
    if(bun) rez = min(rez, abs(slin-elin) + abs(scol-ecol));///daca nu trece prin niciun capat

    for(int i=1;i<=n;i++)
        dist[i][0] = dist[i][1] = INF;
    priority_queue<pair<int,pair<int,int>>> pq;
    dist[slin][0] = scol;
    pq.push({-dist[slin][0], {slin,0}});
    int mnm=scol;
    for(int i=slin;i<=n;i++)
    {
        mnm = min(mnm, l[i]);
        dist[i][1] = abs(i - slin) + (l[i] - mnm);
        pq.push({-dist[i][1],{i,1}});
    }
    mnm=scol;
    for(int i=slin;i>=1;i--)
    {
        mnm = min(mnm, l[i]);
        dist[i][1] = abs(i - slin) + (l[i] - mnm);
        pq.push({-dist[i][1],{i,1}});
    }

    while(!pq.empty())
    {
        int cdist = -pq.top().first, lin = pq.top().second.first, c = pq.top().second.second;
        pq.pop();
        if(cdist != dist[lin][c])
            continue;
        if(c==0)
        {
            if(lin>1 && dist[lin-1][0] > cdist + 1)///move up
            {
                dist[lin-1][0] = cdist + 1;
                pq.push({-dist[lin-1][0],{lin-1,0}});
            }
            if(lin<n && dist[lin+1][0] > cdist + 1)///move down
            {
                dist[lin+1][0] = cdist + 1;
                pq.push({-dist[lin+1][0],{lin+1,0}});
            }


            if(lin>1 && dist[lin-1][1] > cdist + 1)///move left
            {
                dist[lin-1][1] = cdist + 1;
                pq.push({-dist[lin-1][1],{lin-1,1}});
            }

            if(dist[lin][1] > cdist + l[lin])///move right ???
            {
                dist[lin][1] = cdist + l[lin];
                pq.push({-dist[lin][1],{lin,1}});
            }
        }
        else
        {

            if(tori[lin]<=n && dist[tori[lin]][1] > cdist + abs(tori[lin]-lin))///move down
            {
                dist[tori[lin]][1] = cdist + abs(tori[lin]-lin);
                pq.push({-dist[tori[lin]][1],{tori[lin],1}});
            }
            if(tole[lin]>=1 && dist[tole[lin]][1] > cdist + abs(tole[lin]-lin))///move down
            {
                dist[tole[lin]][1] = cdist + abs(tole[lin]-lin);
                pq.push({-dist[tole[lin]][1],{tole[lin],1}});
            }

            if(lin<n && dist[lin+1][0] > cdist + 1)///move right
            {
                dist[lin+1][0] = cdist + 1;
                pq.push({-dist[lin+1][0],{lin+1,0}});
            }

            if(dist[lin][0] > cdist + l[lin])///move left
            {
                dist[lin][0] = cdist + l[lin];
                pq.push({-dist[lin][0],{lin,0}});
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        rez = min(rez, dist[i][0] + abs(i-elin) + ecol);
    }
    mnm=INF;
    for(int i=elin;i<=n;i++)
    {
        mnm = min(mnm, l[i]);
        if(l[i] <= mnm)
        {
            rez = min(rez, dist[i][1] + abs(i-elin) + abs(l[i]-ecol));
        }
    }
    mnm=INF;
    for(int i=elin;i>=1;i--)
    {
        mnm = min(mnm, l[i]);
        if(l[i] <= mnm)
        {
            rez = min(rez, dist[i][1] + abs(i-elin) + abs(l[i]-ecol));
        }
    }
    return rez;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n>>slin>>scol>>elin>>ecol;
    ecol--;
    scol--;
    for(int i=1;i<=n;i++)
        cin>>l[i];
    deque<int> dq;
    for(int i=1;i<=n;i++)
    {
        while(!dq.empty() && l[i] < l[dq.back()])
            dq.pop_back();
        if(dq.empty())
            tole[i]=0;
        else
            tole[i]=dq.back();
        dq.push_back(i);
    }
    dq.clear();
    for(int i=n;i>0;i--)
    {
        while(!dq.empty() && l[i] < l[dq.back()])
            dq.pop_back();
        if(dq.empty())
            tori[i]=n+1;
        else
            tori[i]=dq.back();
        dq.push_back(i);
    }
    cout<<solve();
    return 0;
}
/**

3
1 2
3 2

1
0
1

*/

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