Submission #1177597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177597		alexdd	Text editor (CEOI24_editor)	C++20	45 / 100	4093 ms	70328 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];
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
        {
            mnm=l[lin];
            for(int i=lin+1;i<=n;i++)
            {
                if(l[i] <= mnm)
                {
                    mnm = l[i];
                    if(dist[i][1] > cdist + abs(i-lin))///move down
                    {
                        dist[i][1] = cdist + abs(i-lin);
                        pq.push({-dist[i][1],{i,1}});
                    }
                }
            }
            mnm=l[lin];
            for(int i=lin-1;i>=1;i--)
            {
                if(l[i] <= mnm)
                {
                    mnm = l[i];
                    if(dist[i][1] > cdist + abs(i-lin))///move up
                    {
                        dist[i][1] = cdist + abs(i-lin);
                        pq.push({-dist[i][1],{i,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];
    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: 0 / 11
• Subtask 5: 0 / 44