Submission #1137709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137709		Ghulam_Junaid	Text editor (CEOI24_editor)	C++20	5 / 100	4096 ms	58860 KiB

Main

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

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

vector<pair<int, int>> imp;
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 == len[x]){
            if (nsl[x] <= el and el <= nsr[x])
                imp.push_back({min(y, len[el]), d + abs(x - el)});
        }

        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--;

    vector<pair<int, int>> vec;
    for (int i = 1; i <= n; i ++)
        cin >> len[i], vec.push_back({len[i], i}), nsr[i] = n + 1;
    sort(vec.begin(), vec.end());

    set<int> st;
    for (int i = 0; i < vec.size(); i ++){
        int j = i;
        while (j < vec.size() and vec[j].first == vec[i].first)
            j++;

        for (int k = i; k < j; k ++){
            auto it = st.lower_bound(vec[k].second);
            if (it != st.end())
                nsr[vec[k].second] = *it;
            if (it != st.begin()){
                it--;
                nsl[vec[k].second] = *it;
            }
        }
        for (int k = i; k < j; k ++)
            st.insert(vec[k].second);
    }

    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));
    }
    for (auto [y, d] : imp)
        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