Submission #1040720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040720		elazarkoren	Text editor (CEOI24_editor)	C++17	100 / 100	237 ms	50136 KiB

Main

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;

const ll infinity = 1e18;
const int MAX_N = 1e6 + 5;

ll ans = infinity;

ll a[MAX_N];
ll distl[MAX_N], distr[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    ll sx, sy, ex, ey;
    cin >> n >> sx >> sy >> ex >> ey;
    sx--, sy--, ex--, ey--;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (ll i = sx, j = sy, d = 0; i >= 0; i--, d++) {
        chkmin(j, a[i]);
        if (i == ex) {
            chkmin(ans, d + abs(ey - j));
        }
        distl[i] = d + j;
        distr[i] = d + a[i] - j;
    }
    for (ll i = sx, j = sy, d = 0; i < n; i++, d++) {
        chkmin(j, a[i]);
        if (i == ex) {
            chkmin(ans, d + abs(ey - j));
        }
        distl[i] = d + j;
        distr[i] = d + a[i] - j;
    }
    for (int times = 0; times < 3; times++) {
        deque<pii> stk = {{0, distl[0]}, {a[0], distr[0]}};
        if (!a[0]) stk.pop_back();
        ll offset = 0;
        for (int i = 1; i < n; i++) {
            offset++;
            ll x = min(stk[0].y, stk.back().y);
            ll nx = infinity;
            while (stk.back().x > a[i]) {
                chkmin(nx, stk.back().y);
                stk.pop_back();
            }
            chkmin(nx, stk.back().y + a[i] - stk.back().x);
            chkmin(nx, distr[i] - offset);
            while (!stk.empty() && stk.back().y >= nx + a[i] - stk.back().x) stk.pop_back();
            stk.push_back({a[i], nx});
            if (!stk[0].x) {
                stk.pop_front();
            }
            chkmin(x, distl[i] - offset);
            while (!stk.empty() && stk[0].y >= x + stk[0].x) stk.pop_front();
            stk.push_front({0, x});
            if (stk.back().x != a[i]) {
                stk.push_back({a[i], stk.back().y + a[i] - stk.back().x});
            }
            chkmin(distl[i], stk[0].y + offset);
            chkmin(distr[i], stk.back().y + offset);

            if (i == ex) {
                auto it = lower_bound(all(stk), pii(ey, 0));
                chkmin(ans, it->y + offset + it->x - ey);
                it--;
                chkmin(ans, it->y + offset + ey - it->x);
            }
        }

        stk.clear();
        stk = {{0, distl[n - 1]}};
        offset = 0;
        for (int i = n - 2; i >= 0; i--) {
            offset++;
            ll x = stk[0].y;
            ll nx = stk[0].y;
            while (stk.back().x > a[i]) {
                chkmin(nx, stk.back().y);
                stk.pop_back();
            }
            chkmin(nx, stk.back().y + a[i] - stk.back().x);
            chkmin(nx, distr[i] - offset);
            while (!stk.empty() && stk.back().y >= nx + a[i] - stk.back().x) stk.pop_back();
            stk.push_back({a[i], nx});
            if (!stk[0].x) {
                stk.pop_front();
            }
            chkmin(x, distl[i] - offset);
            while (!stk.empty() && stk[0].y >= x + stk[0].x) stk.pop_front();
            stk.push_front({0, x});
            if (stk.back().x != a[i]) {
                stk.push_back({a[i], stk.back().y + a[i] - stk.back().x});
            }
            chkmin(distl[i], stk[0].y + offset);
            chkmin(distr[i], stk.back().y + offset);

            if (i == ex) {
                auto it = lower_bound(all(stk), pii(ey, 0));
                chkmin(ans, it->y + offset + it->x - ey);
                it--;
                chkmin(ans, it->y + offset + ey - it->x);
            }
        }
    }
    cout << ans << '\n';
}

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