Submission #1040484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040484		isaachew	Text editor (CEOI24_editor)	C++17	100 / 100	2436 ms	375816 KiB

Main

#include <bits/stdc++.h>
/*
 Only ends of lines and beginnings of lines matter
 Go to end higher than current - certain weight
 
 1234567
 1234
 123456789
0
 
 7 goes to 4 only
 9 goes to 4 and 0
 4 goes to 7 and 9
 0 goes to 5 and 9
 */
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;
    std::cin>>n;
    int sr,sc,tr,tc;
    std::cin>>sr>>sc>>tr>>tc;
    sr--,sc--,tr--,tc--;
    std::vector<int> lines;
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        lines.push_back(x);
    }
    std::vector<long long> dists(2*n+2,1e18);
    std::vector<std::vector<std::pair<int,int>>> edges(2*n+2);
    std::vector<int> ilines;
    for(int i=0;i<n;i++){//right points of lines
        while(!ilines.empty()&&lines[ilines.back()]>=lines[i]){//do not use warping
            edges[ilines.back()].push_back({i,i-ilines.back()});
            edges[i].push_back({ilines.back(),i-ilines.back()+lines[ilines.back()]-lines[i]});
            ilines.pop_back();
        }
        if(!ilines.empty()){
            edges[i].push_back({ilines.back(),i-ilines.back()});
            edges[ilines.back()].push_back({i,i-ilines.back()+lines[i]-lines[ilines.back()]});
        }
        ilines.push_back(i);
    }
    for(int i=0;i<n;i++){//left points of lines
        if(i)edges[i+n].push_back({i-1,1});//left
        if(i+1<n)edges[i].push_back({i+1+n,1});//right
        edges[i].push_back({i+n,lines[i]});//straight right/left
        edges[i+n].push_back({i,lines[i]});
        if(i+1<n){
            edges[i+n].push_back({i+n+1,1});//up/down
            edges[i+n+1].push_back({i+n,1});
        }
    }
    int i=sr;
    for(;i>=0&&lines[i]>sc;i--){
        edges[2*n].push_back({i,lines[i]-sc+sr-i});//above and to right
    }
    if(i>=0)edges[2*n].push_back({i,sr-i});//above and to left
    i=sr+1;
    for(;i<n&&lines[i]>sc;i++){
        edges[2*n].push_back({i,lines[i]-sc+i-sr});//below and to right
    }
    if(i<n){
        edges[2*n].push_back({i,i-sr});//below and to left
    }
    edges[2*n].push_back({sr+n,sc});//to left
    
    i=tr;
    for(;i>=0&&lines[i]>tc;i--){
        edges[i].push_back({2*n+1,lines[i]-tc+tr-i});
    }
    if(i>=0){
        edges[i].push_back({2*n+1,tc-lines[i]+tr-i});
    }
    i=tr+1;
    for(;i<n&&lines[i]>tc;i++){
        edges[i].push_back({2*n+1,lines[i]-tc+i-tr});
    }
    if(i<n)edges[i].push_back({2*n+1,tc-lines[i]+i-tr});
    edges[tr+n].push_back({2*n+1,tc});//to right
    
    bool candirect=true;
    for(int i=std::min(sr,tr);i<=std::max(sr,tr);i++){
        if(lines[i]<std::max(sc,tc))candirect=false;
    }
    if(candirect){
        edges[2*n].push_back({2*n+1,std::abs(sr-tr)+std::abs(sc-tc)});
    }
    
    std::priority_queue<std::pair<long long,int>> dijkstra;
    dijkstra.push({0,2*n});
    while(!dijkstra.empty()){
        std::pair<long long,int> cur=dijkstra.top();
        cur.first=-cur.first;
        dijkstra.pop();
        if(cur.first>=dists[cur.second])continue;
        dists[cur.second]=cur.first;
        for(std::pair<int,int> i:edges[cur.second]){
            dijkstra.push({-(cur.first+i.second),i.first});
        }
    }
    std::cout<<dists[2*n+1]<<'\n';
}

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