Submission #2240137

---

Source Code Expand

#include <iostream>
#include <algorithm>
using namespace std;
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
typedef long long LL;
const int MAXN = 2e5+17;
const int MOD = 1e9+7;
LL a[MAXN],dp[MAXN][4],sum[MAXN][4],jmp[MAXN];
int main(int argc ,char const *argv[])
{
    #ifdef noob
    freopen("Input.txt","r",stdin);freopen("Output.txt","w",stdout);
    #endif	
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
    	cin>>a[i];
    }
    sort(a, a+n);
    for (int i = 0; i < n; ++i)
    {
    	dp[i][1] = 1;
    	jmp[i] =  upper_bound(a, a+i+1, a[i]/2 )-a-1;
    	// debug(a[i]);
    	// debug(jmp[i]);
    	// debug(a[jmp[i]]);
    }
    for (int i = 2; i <= 4 ; ++i)
    {
    	sum[0][i-1] = dp[0][i-1];
    	// debug(i);
    	for (int j = 1; j < n; ++j)
    	{
    		// debug(j);
    		sum[j][i-1] = (sum[j-1][i-1]+dp[j][i-1])%MOD;
    		// debug(sum[j][i-1]);
    	}
    	for (int j = 0; j < n; ++j)
    	{
    		if(jmp[j]!=-1) 
    			dp[j][i] = sum[jmp[j]][i-1];
    		// debug(j);
    		// debug(jmp[j]);
    		// debug(dp[j][i]);
    	}
    }
    LL ans = 0;
    for (int i = 0; i < n; ++i)
    {
    	ans = (ans+dp[i][4])%MOD;
    }
    cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result