Good pairs#9642

Good pairs (Editorial)

Let's rewrite the condition $a_{i} + a_{j} > b_{i} + b_{j}$ a_i + a_j > b_i + b_j in the following form:

a_{i} - b_{i} > - (a_{j} - b_{j})

a_i - b_i > – ( a_j - b_j)

Let's construct an array of differences $c$ , where $c_{i} = a_{i} - b_{i}$ c_i = a_i - b_i. Sort the array c in non-decreasing order. The inequality $a_{i} - b_{i} > - (a_{j} - b_{j})$ a_i - b_i > - ( a_j - b_j) is equivalent to $c_{i} > - c_{j}$ c_i > - c_j, or, equivalently, $c_{j} > - c_{i}$ c_j > - c_i. This inequality can also be written as:

c_{i} + c_{j} > 0

c_i + c_j > 0

Now, for each index $i (0 \leq i \leq n - 1)$ i~(0 \le i \le n - 1), we need to find the smallest index $j$ such that $c_{j} > - c_{i}$ c_j > - c_i. For all indices $k$ satisfying $j \leq k \leq n - 1$ j \le k \le n - 1, the pairs $(i, k)$ will be good. However, to avoid counting pairs twice, we should only consider those for which $k > i$ k > i.

Example

Let’s consider the given example. Sort the array $c_{i} = a_{i} - b_{i}$ c_i = a_i - b_i in ascending order.

Let's take $i = 0$ i = 0. We are looking for the smallest index $j$ such that $c_{j} > - c_{0} = 3$ c_j > - c_0 = 3. The smallest such index is $j = 4$ j = 4. Therefore, the index pairs $(0, 4)$ and $(0, 5)$ are good.

Let's take $i = 1$ i = 1. We are looking for the smallest index $j$ such that $c_{j} > - c_{1} = 1$ c_j > - c_1 = 1. The smallest such index is $j = 3$ j = 3. Therefore, the index pairs $(1, 3), (1, 4)$ (1, 3), (1, 4) and $(1, 5)$ are good.

Let's take $i = 2$ i = 2. We are looking for the smallest index $j$ such that $c j > - c_{2} = 0$ cj > - c_2 = 0. The smallest such index is $j = 3$ j = 3. Therefore, the index pairs $(2, 3), (2, 4)$ (2, 3), (2, 4) and $(2, 5)$ are good.

Let's take $i = 3$ i = 3. We are looking for the smallest index $j$ such that $c_{j} > - c_{3} = - 3$ c_j > - c_3 = -3. The smallest such index is $j = 1$ j = 1. A pair $(i, k)$ is considered good if two conditions are met: $k \geq j$ k \ge j and $k > i$ k > i. In this case, the good pairs are $(3, 4)$ and $(3, 5)$ . The pairs $(3, 1)$ and $(3, 2)$ are also good, but they have already been counted earlier when considering $i = 1$ i = 1 (pair $(1, 3)$ ) and $i = 2$ i = 2 (pair $(2, 3)$ ).

Let's take $i = 4$ i = 4. The only good pair in this case is $(4, 5)$ .

In total, there are $11$ good index pairs.

Algorithm implementation

Read the input data.

scanf("%d", &n);
a.resize(n); b.resize(n); 
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);
for (i = 0; i < n; i++)
  scanf("%d", &b[i]);

Build an array of differences $c$ , where $c_{i} = a_{i} - b_{i}$ c_i = a_i - b_i.

c.resize(n);
for (i = 0; i < n; i++)
  c[i] = a[i] - b[i];

Sort the array $c$ in ascending order.

sort(c.begin(), c.end());

Count the number of good index pairs in the variable $r es$ .

res = 0;

Iterate over the indices $i$ .

for (i = 0; i < n; i++)
{

For each index $i$ , find the smallest index $p os$ such that $c_{p os} > - c_{i}$ c_{pos} > - c_i. At the same time, the condition $p os \geq i + 1$ pos \ge i + 1 must be satisfied.

  pos = lower_bound(c.begin() + i + 1, c.end(),-c[i] + 1) - c.begin();

All index pairs $(i, k)$ such that $p os \leq k \leq n - 1$ pos \le k \le n - 1 will be good. The number of such values of $k$ is $(n - 1) - p os + 1 = n - p os$ (n - 1) - pos + 1 = n - pos.

  res += n - pos;
}

Print the answer.

printf("%lld\n", res);