Submission #1137661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137661		Ghulam_Junaid	Text editor (CEOI24_editor)	C++20	5 / 100	4104 ms	278784 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10; // 3e6
int n, len[N], sl, sc, el, ec;

map<pair<int, int>, int> dist;
set<pair<int, pair<int, int>>> st;

inline int distance(int x, int y){
    if (dist.find({x, y}) == dist.end())
        dist[{x, y}] = 2e9;
    return dist[{x, y}];
}

inline void upd(int x, int y, int nd){
    if (x <= 0 or n < x or y < 0 or len[x] < y) return;
    if (distance(x, y) > nd){
        st.erase({dist[{x, y}], {x, y}});
        dist[{x, y}] = nd;
        st.insert({dist[{x, y}], {x, y}});
    }
}

void dijkstra(int x, int y){
    upd(x, y, 0);
    while (!st.empty()){
        auto [d, P] = *st.begin();
        auto [x, y] = P;
        st.erase(st.begin());

        upd(x, 0, d + y);
        upd(x, len[x], d + len[x] - y);

        if (y == 0){
            upd(x - 1, 0, d + 1);
            upd(x + 1, 0, d + 1);
            upd(x - 1, len[x - 1], d + 1);
        }
        else if (y == len[x]){
            upd(x + 1, 0, d + 1);
            if (len[x - 1] <= len[x])
                upd(x - 1, len[x - 1], d + 1);
            if (len[x + 1] <= len[x])
                upd(x + 1, len[x + 1], d + 1);
        }
        else{
            upd(x - 1, min(len[x - 1], y), d + 1);
            upd(x + 1, min(len[x + 1], y), d + 1);
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> sl >> sc >> el >> ec;
    sc--, ec--;
    for (int i = 1; i <= n; i ++)
        cin >> len[i];

    dijkstra(sl, sc);

    int ans = 2e9;
    for (auto [P, d] : dist){
        auto [x, y] = P;
        if (x != el) continue;
        ans = min(ans, d + abs(y - ec));
    }
    cout << ans << endl;
}

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