Submission #3591561

---

Source Code Expand

#include<bits/stdc++.h>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		 int F=1,n=0;
		 char ch;
		 while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		 ch=='-'?F=0:n=ch-'0';
		 while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		 return F?n:-n;
	}
	long long G()
	{
		 long long F=1,n=0;
		 char ch;
		 while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		 ch=='-'?F=0:n=ch-'0';
		 while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		 return F?n:-n;
	}
}
int R(int l,int r)
{
	return (rand()<<15|rand())%(r-l+1)+l;
}
long long h[222222];
int tot;
void push(long long v)
{
	h[++tot]=v;
	std::push_heap(h+1,h+tot+1);
}
long long pop()
{
	std::pop_heap(h+1,h+tot+1);
	return h[tot--];
}
long long add;
int main()
{
	unsigned long long s0=0,len;
	long long x;
	int n=io::F();
	{
		int l=io::F(),r=io::F();
		push(l);
		push(l);
		len=r-l;
		x=0,s0=l;
	}
	for(register int i=2;i<=n;++i)
	{
		int l=io::F(),r=io::F();
		long long tmp=pop()+add;
		tmp+=len;
		len=r-l;
		add-=len;
		x-=len;
		push(tmp-add);
		push(l-add);
		push(l-add);
		s0+=l-x;
		pop();
	}
	std::sort(h+1,h+tot+1); 
	for(register int i=n;i;--i)
	{
		long long tmp=h[n+1-i]+add;
		s0-=(tmp-x)*i;
		x=tmp;
	}
	printf("%lld\n",s0);
	return 0;
}

Submission Info

Judge Result