Submission #1152854

---

Source Code Expand

#include<iostream>
#include<algorithm>
using namespace std;
long M=1e9+7,d[1<<17],a[1<<17],x[1<<17];
main()
{
	int n;cin>>n;
	for(int i=0;i<n;i++)cin>>d[i];
	sort(d,d+n);
	long b=0;
	for(int i=0;i<n;i++)
	{
		for(;b<n&&d[i]*2>d[b];b++);
		a[i]=n-b;x[i]=b;
	}
	for(int i=n-1;i;i--)a[i-1]+=a[i];
	//for(int i=0;i<30;i++)cout<<i<<" : "<<a[i]<<endl;
	b=0;long ans=0;
	for(int i=0;i<n;i++)
	{
		for(;d[b]*2<=d[i];b++);
		ans=(ans+b*a[x[i]]%M)%M;
	}
	cout<<ans<<endl;
}

Submission Info

Judge Result