Submission #1980553

---

Source Code Expand

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

typedef long long ll;

ll ans;

struct slope {
	priority_queue <ll> pq;
	ll delta;

	void upd(ll x) { delta += x; }
	void push(ll x) { pq.push(x - delta); }
	ll top() { return pq.top() + delta; }
	void pop() { pq.pop(); }

	void debug() {
		cerr << "\tdelta = " << delta << endl;
		priority_queue <ll> tmp = pq;
		cerr << "\tDEBUG\n";
		cerr << "\t";
		while(!tmp.empty()) {
			cerr << abs(tmp.top() + delta) << ' ';
			tmp.pop();
		}
		cerr << endl;
	}
} lef, rig;

const int N = 1e5 + 5;
int n;
ll l[N], r[N];

ll cost(ll l, ll r, ll x) {
	if (x < l) return l - x;
	if (x > r) return x - r;
	return 0;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i];

	lef.push(l[1]);
	rig.push(-l[1]);

	for (int i = 2; i <= n; ++i) {
		lef.upd(l[i] - r[i]);
		rig.upd(-(r[i - 1] - l[i - 1]));

		ans += cost(lef.top(), -rig.top(), l[i]);

		lef.push(l[i]);
		rig.push(-l[i]);

		while(lef.top() > -rig.top()) {
			ll x = lef.top(); lef.pop();
			ll y = -rig.top(); rig.pop();
			lef.push(y); rig.push(-x);
		}
	}

	cout << ans << endl;
}

Submission Info

Judge Result