Submission #1237355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237355		The_Samurai	Text editor (CEOI24_editor)	C++20	100 / 100	2648 ms	95868 KiB

Main

#include "bits/stdc++.h"
using namespace std;
const int inf = INT_MAX;

struct segtree {
    vector<int> tree;
    int size;

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size, inf);
    }

    void upd(int p, int v) {
        tree[p + size] = v;
        for (p += size; p > 1; p >>= 1) tree[p >> 1] = min(tree[p], tree[p ^ 1]);
    }

    int get(int l, int r) {
        if (l > r) swap(l, r);
        int res = inf;
        for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = min(res, tree[l++]);
            if (r & 1) res = min(res, tree[--r]);
        }
        return res;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n, sx, sy, tx, ty;
    cin >> n >> sx >> sy >> tx >> ty;
    sy--; ty--;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    priority_queue<tuple<int, int, int>> pq;
    pq.emplace(0, sx, sy);
    vector<pair<int, int>> all;
    auto id = [&](pair<int, int> x) -> int {
        return lower_bound(all.begin(), all.end(), x) - all.begin();
    };
    
    segtree sg; sg.init(n + 1);
    for (int i = 1; i <= n; i++) sg.upd(i, a[i]);
    for (int i = 1; i <= n; i++) {
        all.emplace_back(i, 0);
        all.emplace_back(i, a[i]);
        all.emplace_back(i, min(sy, sg.get(i, sx)));
    }
    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());
    vector<int> dist(all.size(), inf);
    auto add = [&](int d, int x, int y) -> bool {
        int i = id({x, y});
        if (dist[i] > d) {
            dist[i] = d;
            pq.emplace(-d, x, y);
            return true;
        }
        return false;
    };
    
    dist[id({sx, sy})] = 0;

    int ans = inf;
    while (!pq.empty()) {
        auto [d, x, y] = pq.top(); pq.pop();
        d *= -1;
        if (dist[id({x, y})] < d) continue;
        // cout << d << ' ' << x << ' ' << y << ' ' << sg.get(x, tx) << endl;
        ans = min(ans, d + abs(x - tx) + abs(min(y, sg.get(x, tx)) - ty));
        bool found = false;
        if (y > 0) found = found | add(d + y, x, 0);
        else if (x > 1) found = found | add(d + 1, x - 1, a[x - 1]);
        if (y < a[x]) found = found | add(d + a[x] - y, x, a[x]);
        else if (x < n) found = found | add(d + 1, x + 1, 0);
        if (found or y == min(sy, sg.get(x, sx)) or y == 0) {
            if (x > 1) add(d + 1, x - 1, min(y, a[x - 1]));
            if (x < n) add(d + 1, x + 1, min(y, a[x + 1]));
            continue;
        }
        // if (x > 1 and y >= a[x - 1]) pq.emplace(-d - 1, x - 1, a[x - 1]);
        // if (x < n and y >= a[x + 1]) pq.emplace(-d - 1, x + 1, a[x + 1]);
        // if (x > 1 and (found or min(y, a[x - 1]) == a[x - 1])) add(d + 1, x - 1, min(y, a[x - 1]));
        // if (x < n and (found or min(y, a[x + 1]) == a[x + 1])) add(d + 1, x + 1, min(y, a[x + 1]));
    }
    assert(ans < inf);
    cout << ans;
}

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