Submission #1211968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211968		yanb	Text editor (CEOI24_editor)	C++20	56 / 100	2121 ms	556576 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

using pii = pair<int, int>;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n, sx, sy, ex, ey;
    cin >> n >> sy >> sx >> ey >> ex;
    sy--; sx--; ey--; ex--;

    vector<int> l(n);
    for (int i = 0; i < n; i++) cin >> l[i];

    vector<int> xd(n + 2);
    for (int i = 0; i < n; i++) xd[i] = l[i];
    xd[n] = sx;
    xd[n + 1] = ex;
    sort(xd.begin(), xd.end());
    xd.erase(unique(xd.begin(), xd.end()), xd.end());
    int m = xd.size();

    vector<int> ld(n);
    for (int i = 0; i < n; i++) {
        ld[i] = lower_bound(xd.begin(), xd.end(), l[i]) - xd.begin();
    }
    int sxd = lower_bound(xd.begin(), xd.end(), sx) - xd.begin();
    int exd = lower_bound(xd.begin(), xd.end(), ex) - xd.begin();

    vector<vector<pii>> g(n * m); // {y, x}
    for (int y = 0; y < n; y++) {
        for (int x = 0; x <= ld[y]; x++) {
            if (y > 0) {
                g[y * m + x].emplace_back((y - 1) * m + min(x, ld[y - 1]), 1);
            }
            if (y < n - 1) {
                g[y * m + x].emplace_back((y + 1) * m + min(x, ld[y + 1]), 1);
            }
            if (x > 0) {
                g[y * m + x].emplace_back(y * m + x - 1, xd[x] - xd[x - 1]);
            } else if (y > 0) {
                g[y * m + x].emplace_back((y - 1) * m + ld[y - 1], 1);
            }
            if (x < ld[y]) {
                g[y * m + x].emplace_back(y * m + x + 1, xd[x + 1] - xd[x]);
            } else if (y < n - 1) {
                g[y * m + x].emplace_back((y + 1) * m, 1);
            }
        }
    }

    priority_queue<pii, vector<pii>, greater<pii>> q;
    vector<int> d(n * m, 1e17);
    q.emplace(0, sy * m + sxd);
    while (!q.empty()) {
        auto [dv, v] = q.top();
        q.pop();
        if (d[v] > dv) {
            d[v] = dv;
            for (auto [u, vu] : g[v]) {
                q.emplace(dv + vu, u);
            }
        }
    }

    cout << d[ey * m + exd] << "\n";
}

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