Count the triplets#9022

Count the triplets (Editorial)

Let's sort all three arrays. For each element $b_{j}$ b_j, use binary search to determine:

the number of elements $x$ in array $a$ that are less than $b_{j}$ b_j,
the number of elements $y$ in array $c$ that are greater than $b_{j}$ b_j.

Then, for a fixed value of $b_{j}$ b_j, there are exactly $x * y$ x * y triplets of the form $(a_{i}, b_{j}, c_{k})$ (a_i, b_j, c_k) that satisfy the inequality $a_{i} < b_{j} < c_{k}$ a_i < b_j < c_k.

Example

Let's consider the sorted arrays and compute the number of valid triplets for $b_{5} = 10$ b_5 = 10.

We have: $a_{i} < b_{5}$ a_i < b_5 for $i \leq 5$ i \le 5, and $c_{k} > b_{5}$ c_k > b_5 for $k \geq 7$ k \ge 7.

Thus, the inequality $a_{i} < b_{5} < c_{k}$ a_i < b_5 < c_k holds for $1 \leq i \leq 5$ 1 \le i \le 5 and $7 \leq k \leq 8$ 7 \le k \le 8.

The number of triplets $(a_{i}, b_{5}, c_{k})$ (a_i, b_5, c_k) is $5 * 2 = 10$ 5 * 2 = 10.

Algorithm implementation

Declare the arrays.

#define MAX 100000
int a[MAX], b[MAX], c[MAX];

Read the input data.

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

Sort the arrays.

sort(a, a + n);
sort(b, b + n);
sort(c, c + n);

Count the number of valid triplets using the variable $r es$ . Iterate over the values of $b_{j}$ b_j.

res = 0;
for (j = 0; j < n; j++)
{

The number of elements in array $a$ that are less than $b_{j}$ b_j is $x$ .

  x = lower_bound(a, a + n, b[j]) - a;

The number of elements in array $c$ that are greater than $b_{j}$ b_j is $y$ .

  y = n - (upper_bound(c, c + n, b[j]) - c);

Then, for the given value of $b_{j}$ b_j, there are exactly $x * y$ x * y valid triplets.

  res += x * y;
}

Print the answer.

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

Java implementation

import java.util.*;

public class Main 
{
  static int lower_bound(int m[], int start, int end, int x)
  {
    while (start < end)
    {
      int mid = (start + end) / 2;
      if (x <= m[mid])
         end = mid;
      else
        start = mid + 1;
    }
    return start;
  }

  static int upper_bound(int m[], int start, int end, int x)
  {
    while (start < end)
    {
      int mid = (start + end) / 2;
      if (x >= m[mid])
        start = mid + 1;
      else
        end = mid;
    }
    return start;
  }

  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);    
    int i, n = con.nextInt();
    int a[] = new int[n];
    for(i = 0; i < n; i++) a[i] = con.nextInt();

    int b[] = new int[n];
    for(i = 0; i < n; i++) b[i] = con.nextInt();

    int c[] = new int[n];
    for(i = 0; i < n; i++) c[i] = con.nextInt();

    Arrays.sort(a); Arrays.sort(b); Arrays.sort(c);
    
    long res = 0;
    for (i = 0; i < n; i++)
    {
      int x = lower_bound(a, 0, n, b[i]);
      int y = n - (upper_bound(c, 0, n, b[i]));
      res += 1L * x * y;
    }
    
    System.out.println(res);
    con.close();
  }
}

Java