Submission #593005

#	Time	Username	Problem	Language	Result	Execution time	Memory
593005		penguinhacker	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	171 ms	14944 KiB

bulves

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=5e5;
int n, a[mxN], b[mxN];
priority_queue<ll> pq;
ll ans, shift;

void dbg() {
	priority_queue<ll> pq2=pq;
	vector<ll> vals;
	while(pq2.size()) {
		vals.push_back(pq2.top()+shift);
		pq2.pop();
	}
	reverse(vals.begin(), vals.end());
	cout << ans << "\n";
	for (ll i : vals)
		cout << i << " ";
	cout << endl;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	pq.push(0);
	for (int i=0; i<n; ++i) {
		cin >> a[i] >> b[i];
		int d=b[i]-a[i];
		pq.pop();
		shift+=d;
		ans+=max(0ll, pq.top()+shift);
		if (shift>0)
			pq.push(0);
		else {
			pq.push(-shift);
			pq.push(-shift);
		}
		//dbg();
	}
	pq.pop();
	ll last=pq.top()+shift, slope=0;
	for (; last; pq.pop()) {
		ll x=pq.top()+shift;
		ans+=(last-x)*slope;
		++slope;
		last=x;
	}
	cout << ans;
	return 0;
}

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36