Submission #1262270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262270		kikitop1gg	Text editor (CEOI24_editor)	C++17	100 / 100	2465 ms	472832 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define vpp vector<pair<ll, pair<ll, ll>>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define sc set<char>
#define mod 1000000007
#define inf 1000000000000000000
#define all(x) (x).begin(), (x).end()

ll get_min(ll l, ll r, ll k, ll a, ll b, vi& tree) {
    if(r < a || b < l) return inf;
    if(a <= l && r <= b) return tree[k];
    ll d = (l + r) / 2;
    return min(get_min(l, d, 2 * k, a, b, tree), get_min(d + 1, r, 2 * k + 1, a, b, tree));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin >> n;
    ll sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;
    sx--; sy--; ex--; ey--;
    vi a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    ll size = pow(2, ceil(log2(n)));
    vi tree(size * 2, inf);
    for(int i = 0; i < n; i++) tree[i + size] = a[i];
    for(int i = size - 1; i > 0; i--) tree[i] = min(tree[i * 2], tree[i * 2 + 1]);

    ll ans = inf;
    
    // Try manhattan distance
    if(get_min(0, size - 1, 1, min(sx, ex), max(sx, ex), tree) >= min(sy, ey)) {
        ans = abs(sx - ex) + abs(sy - ey);
    }

    struct PairHash {
        size_t operator()(const pp &p) const noexcept {
            return ((uint64_t)p.first << 32) ^ (uint64_t)p.second;
        }
    };
    unordered_map<pp, ll, PairHash> coor;    
    ll nextCoor = 2;
    coor[{sx, sy}] = 0;
    coor[{ex, ey}] = 1;
    ll startInd = 0, endInd = 1;
    for(int i = 0; i < n; i++) {
        if(!(sx == i && sy == 0) && !(ex == i && ey == 0)) {
            coor[{i, 0}] = nextCoor;
            nextCoor++;
        }
        if(a[i] > 0) {
            if(!(sx == i && sy == a[i]) && !(ex == i && ey == a[i])) {
                coor[{i, a[i]}] = nextCoor;
                nextCoor++;
            }
        }
    }
    vector<vp> g(nextCoor);
    vi dists(nextCoor, inf);

    if(sy != 0) {
        g[startInd].push_back({coor[{sx, 0}], sy});
        g[coor[{sx, 0}]].push_back({startInd, sy});
    }
    if(ey != 0) {
        g[endInd].push_back({coor[{ex, 0}], ey});
        g[coor[{ex, 0}]].push_back({endInd, ey});
    }

    for(int i = 0; i < n - 1; i++) {
        ll ind1 = coor[{i, 0}];
        ll ind2 = coor[{i + 1, 0}];
        g[ind1].push_back({ind2, 1});
        g[ind2].push_back({ind1, 1});
        if(a[i] > 0) {
            ind2 = coor[{i, a[i]}];
            g[ind1].push_back({ind2, a[i]});
            g[ind2].push_back({ind1, a[i]});
        }
        ind1 = coor[{i, a[i]}];
        ind2 = coor[{i + 1, 0}];
        g[ind1].push_back({ind2, 1});
        g[ind2].push_back({ind1, 1});
    }

    for(ll i = 0; i < n; i++) {
        ll ind = coor[{i, a[i]}];
        ll dist = abs(sx - i) + a[i] - min(sy, get_min(0, size - 1, 1, min(i, sx), max(i, sx), tree));
        g[startInd].push_back({ind, dist});

        dist = abs(ex - i) + abs(ey - get_min(0, size - 1, 1, min(i, ex), max(i, ex), tree));
        g[ind].push_back({endInd, dist});
    }

    dists[startInd] = 0;
    priority_queue<pp> q;
    q.push({0, startInd});
    vp dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    while(q.size()) {
        ll cur = -q.top().first, v = q.top().second;
        q.pop();
        if(dists[v] < cur) continue;
        
        for(auto[x, cost] : g[v]) {
            if(dists[x] > cur + cost) {
                dists[x] = cur + cost;
                q.push({-(cur + cost), x});
            }
        }
    }

    ans = min(ans, dists[endInd]);

    cout << ans << '\n';
    return 0;
}

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