제출 #776011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776011		danikoynov	Safety (NOI18_safety)	C++14	100 / 100	219 ms	21752 KiB

safety

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll inf = LLONG_MAX;

struct slope_trick
{
    multiset < ll > left_slope, right_slope;
    ll height, left_offset, right_offset;

    slope_trick()
    {
        height = left_offset = right_offset = 0;
    }

    ll get_left()
    {
        if (left_slope.empty())
            return - inf;
        return *left_slope.rbegin() + left_offset;
    }

    ll get_right()
    {
        if (right_slope.empty())
            return inf;
        return *right_slope.begin() + right_offset;
    }

    void add_basic(ll value)
    {
        ll left = get_left(), right = get_right();

        if (value >= left && value <= right)
        {
            left_slope.insert(value - left_offset);
            right_slope.insert(value - right_offset);
        }
        else
        if (value < left)
        {
            left_slope.insert(value - left_offset);
            left_slope.insert(value - left_offset);

            right_slope.insert(left - right_offset);
            left_slope.erase(left_slope.find(left - left_offset));

            height = height + abs(left - value);
        }
        else
        if (value > right)
        {
            right_slope.insert(value - right_offset);
            right_slope.insert(value - right_offset);

            left_slope.insert(right - left_offset);
            right_slope.erase(right_slope.find(right - right_offset));

            height = height + abs(right - value);
        }
    }

    void minimum_interval(ll d)
    {
        left_offset -= d;
        right_offset += d;
    }
};

const int maxn = 2e5 + 10;

int n, a[maxn], d;
void solve()
{
    cin >> n >> d;
    slope_trick st;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        st.minimum_interval(d);
        st.add_basic(a[i]);
    }

    cout << st.height << endl;
}

int main()
{
    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