C. A Tale of Two Lands

自己推出规律后，用O（n^2)实现求解，会超时。upper_bound()是个好的二分查找函数！

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int MAXN = 2e5+10;
 
int a[MAXN];
//lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。
//
//在从小到大的排序数组中，
//
//lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
//
//upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
//
//在从大到小的排序数组中，重载lower_bound()和upper_bound()
//
//lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
//
//upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

int main()
{
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++)
        cin >> a[i], a[i] = abs(a[i]);
    sort(a+1, a+1+n);
    LL res = 0;
    for (int i = 1;i <= n;i++)
        res += (upper_bound(a+1, a+1+n, 2*a[i])-a)-i-1;
    cout << res << endl;
    return 0;
}

在下菜鸡的超时代码：

#include <bits/stdc++.h>
#define fill(x,c) memset(x,c,sizeof(x))
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
int a[200010];
int t,n;
int MOD = 1e9+7;
const int SIZE = 1e6+10;
int main(){
	cin>>n;
	map<int,int> nums;
	REP(i,n){
		scanf("%d",&t);
		nums[abs(t)]++;
	}
	ll ans=0;
	int pre[200010];
	fill(pre,0);
	pre[0] = 0;
	int cnt=1;
	for(auto num1:nums){
		pre[cnt] +=pre[cnt-1]+num1.second;
		cnt++;
	}
	int p=0;
	for(auto num1:nums){
		int y = num1.first;
		int counter = 0;
		p++;
		for(auto num2:nums){
			if(y==num2.first)
			{
				ans+=(num1.second*(num1.second-1))/2;
				break;
			}
			counter++;
			if(y<=2*num2.first){
				ans += num1.second*(pre[p-1]-pre[counter-1])+(num1.second*(num1.second-1))/2;
				break;
			}
		}
	}
	cout<<ans;
	return 0;
}