Submission #1586684

---

Source Code Expand

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:

priority_queue<ll> lft;
priority_queue<ll,vector<ll>,greater<ll>> rht;
ll lo = 0LL, ro = 0LL;
ll ans = 0LL;

const int limit = 100010;
ll l[limit],r[limit],p[limit];

int main(void){
	int n;
	cin >> n;

	rep(i,n){
		cin >> l[i] >> r[i];
		p[i] = r[i] - l[i];
	}

	lft.push(l[0]-lo);
	rht.push(l[0]-ro);
	

	rep(i,1,n){
		lo -= p[i],ro += p[i-1];
		
		lft.push(l[i]-lo);
		rht.push(l[i]-ro);
	
		while(lft.top() + lo > rht.top() + ro){
			ll L = lft.top() + lo, R = rht.top() + ro;
			lft.pop(),rht.pop();
			ans += L - R;
			lft.push(R - lo), rht.push(L - ro);
		}
	}


	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result