Submission #1320697

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<set>
using namespace std;

#define sz(x) (int)(x.size())
#define rep(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
typedef long long ll;
//////////////////////

int const N = 1e5 + 41;

int l[N], r[N], n;
ll pref[N];
int tim;

ll getPref(int l, int r){
	ll ret = pref[r];
	if(l > 0) ret -= pref[l-1];
	return ret;
}

struct S{
	ll x, type, time;
	S(){};
	S(ll x, ll type, ll time) : x(x), type(type), time(time) {};
	bool operator<(const S &s) const {
		return getX() < s.getX();
	};

	ll getX() const {
		if(type == 0){
			return x - getPref(time+1, tim);
		}else{
			return x + getPref(time, tim-1);
		}
	}
};

multiset<S> lp, rp;

ll getLast(multiset<S> &ms){
	multiset<S> :: iterator it = ms.end();
	--it;
	return ((*it).getX());
}

ll getFirst(multiset<S> &ms){
	auto it = ms.begin();
	return (*it).getX();
}

void solve(){
	cin >> n;
	rep(i, 0, n) cin >> l[i] >> r[i];
	rep(i, 0, n) pref[i] = (r[i] - l[i] + (i > 0 ? pref[i-1] : 0));
	ll ans = 0;

	lp.insert(S(l[0], 0, 0));
	rp.insert(S(l[0], 1, 0));
	rep(i, 1, n){
		tim = i;
		if(l[i] >= getLast(lp) && l[i] <= getFirst(rp)){
			lp.insert(S(l[i], 0, i));
			rp.insert(S(l[i], 1, i));
		}else if(l[i] >= getFirst(rp)){
			ans += (l[i] - getFirst(rp));
			S tmp = (*rp.begin());
			tmp.type = 0;
			tmp.x = tmp.getX();
			tmp.time = i;
			rp.erase(rp.begin());
			lp.insert(tmp);
			rp.insert(S(l[i], 1, i));
			rp.insert(S(l[i], 1, i));
		}else{
			ans += (getLast(lp) - l[i]);
			auto it = lp.end();
			--it;
			S tmp = (*it);
			tmp.type = 1;
			tmp.x = tmp.getX();
			tmp.time = i;
			lp.erase(it);
			rp.insert(tmp);
			lp.insert(S(l[i], 0, i));
			lp.insert(S(l[i], 0, i));
		}
	}

	cout << ans << endl;
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

	solve();

	return 0;
}

Submission Info

Judge Result