Submission #471857

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
	int mod = 1e9 + 7;
	int n;
	cin >> n;
	vector<int> d(n);
	int i = 0;
	while ( i < n) {
		int val;
		cin >> val;
		d[i++] = val;
	}
	sort(d.begin(), d.end());
	vector<int> dist(n, n);
	for (int i = 0; i < n - 1; ++i) {
		int val = d[i];
		auto ret = lower_bound(vector<int>::iterator(&d[i + 1]), d.end(), 2 * val);
		if (ret != d.end()) 
			dist[i] = ret - d.begin();
		else
			break;	
	}
	vector<vector<int>> res(n, vector<int>(3));
	for (int i = n - 1; i >= 0 ; --i) {
		int nextpos = dist[i];
		if (nextpos < n) { 
			res[i][0] = n - nextpos;
			res[i][1] =  res[nextpos][0];
			res[i][2] =  res[nextpos][1];
		}
		if (i != n - 1) {
			res[i][0] = (res[i][0] + res[i + 1][0]) % mod;
			res[i][1] = (res[i][1] + res[i + 1][1]) % mod;
			res[i][2] = (res[i][2] + res[i + 1][2]) % mod;
		}
	}
	cout << res[0][2] << endl;
	return 0;
#if 0
	int count = 0;
	for (int i = 0; i < n - 3; ++i) {
		for (int j = dist[i]; j < n - 2; ++j)
			for (int k = dist[j]; k < n - 1; ++k) 
				for (int l = dist[k]; l < n; ++l) {
					count++;
					if (count == 1000000007) 
						count = 0;
				}	
	}
	cout << count << endl;
#endif
	return 0;
}

Submission Info

Judge Result