Submission #1749451

---

Source Code Expand

#include <bits/stdc++.h>
#define inf (1ll<<56)
using namespace std;
typedef long long ll;
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
int n,l,r,tl,tr,L,R,len,ans;
priority_queue <ll> q1;
priority_queue <ll, vector<ll>, greater<ll> > q2;
int main()
{
	n=read(); while(n--)
	{
		l=read(); r=read(); len=r-l;
		tr+=len;
		q1.push(r-tl); q2.push(r-tr);
		while((L=q1.top()+tl)>(R=q2.top()+tr))
		{
			ans+=L-R;
			q1.pop(); q2.pop();
			q1.push(R-tl); q2.push(L-tr);
		}
		tl-=len;
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result