Submission #319756

#	Time	Username	Problem	Language	Result	Execution time	Memory
319756		kostia244	Safety (NOI18_safety)	C++17	100 / 100	321 ms	21304 KiB

safety

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1<<30;
struct sset : public multiset<ll> {
	ll bias = 0;
	void insert(int x) {
		multiset<ll>::insert(x-bias);
	}
	ll get_min() {
		return *begin() + bias;
	}
	void pop_min() {
		erase(find(*begin()));
	}
	ll get_max() {
		return *rbegin() + bias;
	}
	void pop_max() {
		erase(find(*rbegin()));
	}
	void add(ll x) {
		bias += x;
	}
};
int main() {
	cin.tie(0)->sync_with_stdio(0);
	ll n, h, x;
	sset L, R;
	cin >> n >> h >> x;
	L.insert(x);
	R.insert(x);
	ll ans = 0;
	for(int I = 1; I < n; I++) {
		R.add(h);
		L.add(-h);
		cin >> x;
		if(x <= L.get_max()) {
			L.insert(x);
			L.insert(x);
			ans += abs(L.get_max()-x);
			R.insert(L.get_max());
			L.pop_max();
		} else {
			R.insert(x);
			R.insert(x);
			ans += abs(R.get_min()-x);
			L.insert(R.get_min());
			R.pop_min();
		}
	}
	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