Submission #1231097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231097		PVM_pvm	Text editor (CEOI24_editor)	C++20	16 / 100	1349 ms	487880 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1'000'100
int n;
int ln[MAXN];
int sl,sc;
int el,ec;
map<int,int> pos;
vector<int> neo;
vector<pair<pair<int,int>,int>> v[MAXN][6];
long long dst[MAXN][6];
int myL[MAXN];
#define v1 v[rd][ps][q].first.first
#define v2 v[rd][ps][q].first.second
#define vl v[rd][ps][q].second
int main()
{
    cin>>n;
    cin>>sl>>sc;
    cin>>el>>ec;
    pos[sc]=1;
    pos[ec]=1;
    pos[1]=1;
    for (int q=1;q<=n;q++)
    {
        cin>>ln[q];
        pos[ln[q]+1]=1;
    }
    auto cr=pos.begin();
    while (true)
    {
        if (cr==pos.end()) break;
        neo.push_back( cr->first );
        cr++;
    }
    for (int q=1;q<=n;q++)
    {
        for (int w=0;w<neo.size();w++)
        {
            dst[q][w]=-1;
            if ((ln[q]+1)==neo[w])
            {
                myL[q]=w;
            }
        }
    }
    //cout<<neo.size()<<"\n";
    //for (int q=0;q<neo.size();q++) cout<<neo[q]<<" ";
    //cout<<"\n";
    for (int q=1;q<=n;q++)
    {
        for (int w=0;w<neo.size();w++)
        {
            if (neo[w]>(ln[q]+1)) break;
            if (w!=0)
            {
                ///imame rebro nalqvo
                v[q][w].push_back({{q,w-1},neo[w]-neo[w-1]});
            }
            else if (q!=1)
            {
                ///vodi kym pr red
                v[q][w].push_back({ {q-1,myL[q-1]},1 });
            }
            if (w!=neo.size()-1 && neo[w]!=(ln[q]+1))
            {
                ///imame rebro nadqsno
                v[q][w].push_back({{q,w+1},neo[w+1]-neo[w]});
            }
            else if (q!=n)
            {
                ///vodi kym sl red
                v[q][w].push_back({ {q+1,0} ,1 });
            }
            if (q!=1)
            {
                ///imame rebro nadolu
                if (neo[w]>(ln[q-1]+1))
                {
                    v[q][w].push_back({ {q-1,myL[q-1]},1 });
                }
                else
                {
                    v[q][w].push_back({ {q-1,w},1 });
                }
            }
            if (q!=n)
            {
                ///imame rebro nagore
                if (neo[w]>(ln[q+1]+1))
                {
                    v[q][w].push_back({ {q+1,myL[q+1]},1 });
                }
                else
                {
                    v[q][w].push_back({ {q+1,w},1 });
                }
            }
        }
    }

    priority_queue< pair<long long, pair<int,int>>> qu;
    for (int q=0;q<neo.size();q++)
    {
        if (neo[q]==sc)
        {
            sc=q;
            break;
        }
    }
    for (int q=0;q<neo.size();q++)
    {
        if (neo[q]==ec)
        {
            ec=q;
            break;
        }
    }
    //cout<<sc<<" "<<ec<<"\n";
    dst[sl][sc]=0;
    qu.push({0,{sl,sc}});
    while (!qu.empty())
    {
        long long ds=-1*qu.top().first;
        int rd=qu.top().second.first;
        int ps=qu.top().second.second;
        qu.pop();
        if (ds>dst[rd][ps]) continue;
        //cout<<rd<<" "<<ps<<" "<<ds<<"\n";
        for (int q=0;q<v[rd][ps].size();q++)
        {
            if (dst[v1][v2]==-1 || (ds+vl)<dst[v1][v2])
            {
                dst[v1][v2]=ds+vl;
                qu.push({-1*dst[v1][v2],{v1,v2}});
            }
        }
    }
    cout<<dst[el][ec]<<"\n";
}

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