Submission #1294724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294724		doowey	Safety (NOI18_safety)	C++20	100 / 100	132 ms	19192 KiB

safety

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

struct MySet{
    ll b = 0;
    multiset<ll> si;
    void inc(ll x){
        b += x;
    }

    void ins(ll x){
        si.insert(x-b);
    }
    ll get_max(){
        auto it = si.end();
        --it;
        return *it+b;
    }
    ll get_min(){
        auto it = si.begin();
        return *it+b;
    }

    void pop_max(){
        auto it = si.end();
        --it;
        si.erase(it);
    }

    void pop_min(){
        auto it = si.begin();
        si.erase(it);
    }
};

int main(){
    fastIO;
    int n;
    ll h;
    cin >> n >> h;
    ll x;
    MySet L, R;
    ll res = 0;
    for(int i = 1; i <= n; i ++ ){
        cin >> x;
        L.inc(-h);
        R.inc(h);
        if(i > 1){
            ll lf = L.get_max();
            ll rf = R.get_min();
            if(x < lf)
                res += lf - x;
            else if(x > rf)
                res += x - rf;
        }
        L.ins(x);
        R.ins(x);
        while(L.get_max() > R.get_min()){
            ll pi = L.get_max();
            ll qi = R.get_min();
            L.pop_max();
            R.pop_min();
            R.ins(pi);
            L.ins(qi);
        }
    }
    cout << res << "\n";
    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