Submission #1452676

---

Source Code Expand

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

typedef long long ll;

priority_queue<ll> PQL, PQR;
ll pbl, pbr;
ll Ans;
 
int main()
{
	int n;
	cin >> n;

	ll l, r, len;
	for (int i = 0;i < n;i++)
	{
		cin >> l >> r;
		len = r - l;

		pbr += len;
		PQL.push(r - pbl);
		PQR.push(pbr - r);
		while (true) {
			ll L = PQL.top() + pbl;
			ll R = -PQR.top() + pbr;
			if (L <= R)
			{
				break;
			}
			Ans += L - R;
			PQL.pop(), PQR.pop();
			PQL.push(R - pbl), PQR.push(pbr - L);
		}
		pbl -= len;
	}
	
	cout << Ans << endl;
	return 0;
}

Submission Info

Judge Result