Submission #1455959

---

Source Code Expand

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 1000000007
typedef long long ll;
using namespace std;
int main(void){
    ll n;
    ll d[100001];
    ll a[100001],b[100001];
    ll Asum[100001];
    cin>>n;
    for(int i=0;i<n;i++)cin>>d[i];
    sort(d,d+n);
    /*for(int i=0;i<n;i++){
        cout<<d[i]<<endl;
    }*/
    for(int i=0;i<n;i++){
        //lower_bound(d,d+n,2*d[i])で2*d[i]を超える最小の添え字を返す
        //a[i]には2*d[i]を超える要素の個数
        a[i]=n-(lower_bound(d,d+n,2*d[i])-d);
        Asum[i]=a[i];
        //b[i]にはd[i]/2よりも小さな要素の個数
        b[i]=upper_bound(d,d+n,d[i]/2)-d;
    }
    //累積和をとる
    for(int i=n-2;i>=0;i--){
        Asum[i]+=Asum[i+1];
    }
    ll ans=0;
    for(int i=1;i<n-1;i++){
        int idx=lower_bound(d,d+n,2*d[i])-d;
        ans+=b[i]*Asum[idx];
        ans%=MOD;
    }
    cout<<ans<<endl;
}

Submission Info

Judge Result