Submission #409244

#	Time	Username	Problem	Language	Result	Execution time	Memory
409244		VEGAnn	Safety (NOI18_safety)	C++14	100 / 100	239 ms	21112 KiB

safety

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
multiset<ll> let, rit; /// just set (?)
ll ans, h;
int n;

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> h;

    {
        ll x; cin >> x;

        ans = 0;

        let.insert(x);
        rit.insert(x);
    }

    for (ll i = 1; i < n; i++){
        ll x; cin >> x;

        ll lf = (*(--let.end()))  - i * h;
        ll rt = (*(rit.begin())) + i * h;

        if (lf <= x && rt >= x){
            let.insert(x + i * h);
            rit.insert(x - i * h);
        } else if (rt < x){
            ans += abs(rt - x);

            ///  smth

            rit.erase(rit.find(rt - i * h));

            rit.insert(x - i * h);
            rit.insert(x - i * h);

            let.insert(rt + i * h);
        } else {
            assert(lf > x);
            ans += abs(lf - x);

            /// do smth

            let.erase(let.find(lf + i * h));

            let.insert(x + i * h);
            let.insert(x + i * h);

            rit.insert(lf - i * h);
        }
    }

    cout << ans;

    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