Submission #356484

#	Time	Username	Problem	Language	Result	Execution time	Memory
356484		gratus907	Safety (NOI18_safety)	C++17	100 / 100	269 ms	22636 KiB

safety

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;
int INF = 1e15;
const int MN = 202020;
const int LEND = -1e17;
const int REND = 1e17;
int N, H;
int s[MN];
struct mset {
    multiset<int> st;
    string name;
    mset(string _name = "") {
        name = _name;
    }
    int offset;
    int small() {
        return *st.begin() + offset;
    }
    int large() {
        return *st.rbegin() + offset;
    }
    void del(int e) {
        if (e == LEND)
            st.erase(st.begin());
        else if (e == REND)
            st.erase(prev(st.end()));
        else
            st.erase(st.lower_bound(e));
    }
    void ins(int e){
        st.insert(e);
    }
    void print() {
        printf("Print multiset [%s] ", name.c_str());
        for (auto i : st)
            printf("%lld ",i + offset);
        printf("\n");
    }
} l("LEFT"), r("RIGHT");
int32_t main()
{
    usecppio
    cin >> N >> H;
    int MH = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> s[i];
        MH = max(MH, s[i]);
    }
    l.ins(s[1]);
    r.ins(s[1]);
    int ans = 0;
    for (int i = 2; i <= N; i++)
    {
        l.offset -= H;
        r.offset += H;
        int lf = l.large();
        int rf = r.small();
        if (s[i] < lf)
        {
            l.ins(s[i] - l.offset);
            l.ins(s[i] - l.offset);
            l.del(REND);
            r.ins(lf - r.offset);
            ans += abs(lf - s[i]);
        }
        else if (s[i] > rf)
        {
            r.ins(s[i] - r.offset);
            r.ins(s[i] - r.offset);
            r.del(LEND);
            l.ins(rf - l.offset);
            ans += abs(rf - s[i]);
        }
        else
        {
            l.ins(s[i] - l.offset);
            r.ins(s[i] - r.offset);
        }
    }
    cout << ans << '\n';
}

• 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