Submission #574516

#	Time	Username	Problem	Language	Result	Execution time	Memory
574516		timreizin	Safety (NOI18_safety)	C++17	100 / 100	73 ms	5484 KiB

safety

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

#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <vector>
#include <bitset>
#include <string>
#include <algorithm>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <fstream>
#include <numeric>
#include <tuple>
#include <ctime>
#include <random>
#include <array>
#include <cassert>
#include <complex>
#include <valarray>
#include <set>
#include <chrono>

using namespace std;

#define sorti(a) sort((a).begin(), (a).end());
#define reversi(a) reverse((a).begin(), (a).end());
#define yes cout << "Yes\n";
#define no cout << "No\n";
#define ans(a) cout << a << '\n';
#define read(a, n) {(a).resize(n); for (auto &i : a) cin >> i;}
//#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

const int INF = 2147483647;
const ll LONGINF = 9223372036854775807;
const ll MOD = 1e9 + 7;

template <class T>
void output(T pq, ll add, bool order)
{
    cout << "{ ";
    if (order)
    {
        while (!pq.empty())
        {
            cout << pq.top() + add << ", ";
            pq.pop();
        }
    }
    else
    {
        vector<ll> nn;
        while (!pq.empty())
        {
            nn.push_back(pq.top() + add);
            pq.pop();
        }
        while (!nn.empty())
        {
            cout << nn.back() << ", ";
            nn.pop_back();
        }
    }
    cout << "}";
}

void solve()
{
    int n;
    ll h;
    cin >> n >> h;
    pair<ll, ll> f{0, 0};
    priority_queue<ll> pql;
    priority_queue<ll, vector<ll>, greater<>> pqr;
    ll addr = 0, addl = 0;
    /*ll a;
    cin >> a;
    pql.push(a);
    pqr.push(a);*/
    for (int i = 0; i < n; ++i)
    {
        ll a;
        cin >> a;
        //do min
        addl -= h;
        addr += h;
        //add |x-a|
        //{{a}, {0, 0}, {a}}
        ll x = (pql.empty() ? -1e9 - addl : pql.top()) + addl;
        if (a == x)
        {
            pql.push(a - addl);
            pqr.push(a - addr);
        }
        else if (a > x)
        {
            pqr.push(a - addr);
            pqr.push(a - addr);
            //--f.first;
            f.second += a;
            ll x = pqr.top() + addr;
            pqr.pop();
            pql.push(x - addl);
            //-x+ob=nb
            f.second -= x;
        }
        else
        {
            pql.push(a - addl);
            pql.push(a - addl);
            //++f.first;
            f.second -= a;
            ll x = pql.top() + addl;
            pql.pop();
            pqr.push(x - addr);
            //x+ob=nb
            f.second += x;
        }
        /*output(pql, addl, 0);
        cout << ", {" << f.first << ", " << f.second << "}, ";
        output(pqr, addr, 1);
        cout << '\n';*/
    }
    ans(f.second)
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    //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