Submission #1248512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248512		Chris_Black	Safety (NOI18_safety)	C++20	18 / 100	33 ms	2856 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 ans = 0;
ll addl = 0, addr = 0;
priority_queue<int> l;
priority_queue<int, vi, greater<>> r;

///move to left
void shl()
{
    ll t = r.top() + addr;
    r.pop();
    l.push(t - addl);
}

///move to right
void shr()
{
    ll t = l.top() + addl;
    l.pop();
    r.push(t - addr);
}

void show()
{
    vi v;

    while(!l.empty())
    {
        v.pb(l.top() + addl);
        l.pop();
    }

    reverse(v.begin(), v.end());
    for(auto e : v)cout << e << ' ';
    cout << " | ";

    for(auto e : v)l.push(e - addl);
    v.clear();

    while(!r.empty())
    {
        cout << r.top() + addr << ' ';
        v.pb(r.top() + addr);
        r.pop();
    }
    cout << '\n';

    for(auto e : v)r.push(e - addr);
}

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

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

//        cout << "\n";
//        show();
//        cout << " | | | \n";

        ll add = min(l.size() ? abs(l.top() + addl - a[i]) : 0,
                     r.size() ? abs(r.top() + addr - a[i]) : 0);

        ans += add;
        if(l.empty() || a[i] <= l.top() + addl){
            l.push(a[i] - addl);
            l.push(a[i] - addl);
            shr();
            if(l.top() + addl == r.top() + addr && l.top() + addl == a[i])ans -= add;
        }
        else{
            r.push(a[i] - addr);
            r.push(a[i] - addr);
            shl();
            if(l.top() + addl == r.top() + addr && l.top() + addl == a[i])ans -= add;
        }

//        show();
//        cout << '\n';
    }

    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: 0 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 0 / 6
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29