Submission #1249109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249109		Chris_Black	Safety (NOI18_safety)	C++20	100 / 100	52 ms	4464 KiB

safety

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")

#include <bits/stdc++.h>

#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define pii pair<int, int>
#define ff first
#define ss second
#define pll pair<ll, ll>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vpl vector<pll>
#define vvpl vector<vpl>
#define vl vector<ll>
#define vvl vector<vl>
//#define x first
//#define y second


using namespace std;
const int N = 1e6 + 9, LGV = 33, LGN = 21, Mod = 1e9 + 7;
//const int Inf = 0x3f3f3f3f;
const ll Inf = LLONG_MAX / 2;
const bool test_case = false;

//ifstream fin("landscape.in");
//ofstream fout("landscape.out");
//#define cin fin
//#define cout fout

int n, h, a[N];

ll addl, addr;
priority_queue<ll> l;
priority_queue<ll, vl, greater<>> r;

void rebalance()
{
    while(l.size() > r.size())
    {
        r.push(l.top() + addl - addr);
        l.pop();
    }

    while(r.size() > l.size())
    {
        l.push(r.top() + addr - addl);
        r.pop();
    }
}

void add(ll x)
{
    if(l.empty() || x <= l.top() + addl)
        l.push(x - addl);
    else r.push(x - addr);
    rebalance();
}

void solve()
{
    cin >> n >> h;
    FOR(i, 1, n)cin >> a[i];

    ll ans = 0;
    FOR(i, 1, n)
    {
        addl -= h, addr += h;

        if(i > 1)
        {
            ll lp = l.top() + addl, rp = r.top() + addr;
            if(a[i] < lp)ans += lp - a[i];
            else if(a[i] > rp)ans += a[i] - rp;
        }

        add(a[i]);
        add(a[i]);
    }

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t = 1;
    if(test_case)cin >> t;
    while(t --)solve();
    return 0;
}

• 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