Submission #1774705

---

Source Code Expand

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	unsigned long long ans=0;
	int N;
	cin >> N;
	int D[N];
	for(int i=0; i<N; i++){ cin >> D[i];}
	sort(D,D+N);			// O(nlogn)
	int E[N]={0};		//D[N]の２倍以上のものの個数
	int F[N]={0};		//D[N]の1/2倍以下のもの
	int k=0;
	for(int i=0; i<N; i++){
		for(; (k<N && D[k]<2*D[i]); k++){}
		E[i]=N-k;
	}
	k=0;
	for(int i=0; i<N; i++){
		for(; (k<N && D[k]<=D[i]/2) ; k++){}
		F[i]=k;
	}
	

	for(int i=N-E[0]; i<F[N-1]; i++){
		for(int j=F[N-1]-1; 2*D[i]<=D[j]; j--){
			ans+=(F[i]*E[j])%1000000007;
			ans%=1000000007;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result