Submission #580366

#	Time	Username	Problem	Language	Result	Execution time	Memory
580366		islingr	Safety (NOI18_safety)	C++17	100 / 100	66 ms	4356 KiB

safety

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using ld = long double;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b); i-- > (a);)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) static_cast<int>((x).size())

template <class T>
bool uin(T& a, const T& b) {
    return a > b ? a = b, true : false;
}
template <class T>
bool uax(T& a, const T& b) {
    return a < b ? a = b, true : false;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll h;
    cin >> n >> h;

    vector<int> a(n);
    for (auto& x : a) cin >> x;

    priority_queue<ll> L, R;

    ll shift = 0;

    auto push_L = [&](auto y) { L.push(+y + shift); };
    auto push_R = [&](auto y) { R.push(-y + shift); };
    auto get_L = [&]() { return +L.top() - shift; };
    auto get_R = [&]() { return -R.top() + shift; };

    ll val = 0;

    push_L(a[0]);
    push_R(a[0]);
    rep(i, 1, n) {
        const auto x = a[i];

        shift += h;

        const auto tl = get_L();
        const auto tr = get_R();

        if (x < tl) {
            L.pop();
            push_L(x);
            push_L(x);
            push_R(tl);
            val += tl - x;
        } else if (x > tr) {
            R.pop();
            push_R(x);
            push_R(x);
            push_L(tr);
            val += x - tr;
        } else {
            push_L(x);
            push_R(x);
        }
    }

    cout << val << '\n';
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29