Хороші пари#9642

Хороші пари (Розбір)

Перепишемо умову $a_{i} + a_{j} > b_{i} + b_{j}$ a_i + a_j > b_i + b_j в такому вигляді:

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

a_i - b_i > – ( a_j - b_j)

Побудуємо масив різниць $c$ , в якому $c_{i} = a_{i} - b_{i}$ c_i = a_i - b_i. Відсортуємо його за зростанням. Нерівність $a_{i} - b_{i} > - (a_{j} - b_{j})$ a_i - b_i > - ( a_j - b_j) еквівалентно $c_{i} > - c_{j}$ c_i > - c_j, або те ж саме що $c_{j} > - c_{i}$ c_j > - c_i. Це нерівність також можна записати у вигляді:

c_{i} + c_{j} > 0

c_i + c_j > 0

Тепер для кожного індексу $i (0 \leq i \leq n - 1)$ i~(0 \le i \le n - 1) слід знайти мінімальний індекс $j$ , такий що $c_{j} > - c_{i}$ c_j > - c_i. Для всіх індексів $k$ , які задовольняють умову $j \leq k \leq n - 1$ j \le k \le n - 1, пари $(i, k)$ будуть хорошими. Однак, щоб не враховувати пари двічі, слід вибирати тільки ті з них, для яких $k > i$ k > i.

Приклад

Розглянемо наведений приклад. Відсортуємо масив $c_{i} = a_{i} - b_{i}$ c_i = a_i - b_i за зростанням.

Нехай $i = 0$ i = 0. Шукаємо найменший індекс $j$ , такий що $c_{j} > - c_{0} = 3$ c_j > - c_0 = 3. Таким індексом буде $j = 4$ j = 4. Відповідно, пари індексів $(0, 4)$ і $(0, 5)$ будуть хорошими.

Нехай $i = 1$ i = 1. Шукаємо найменший індекс $j$ , такий що $c_{j} > - c_{1} = 1$ c_j > - c_1 = 1. Таким індексом буде $j = 3$ j = 3. Відповідно, пари індексів $(1, 3), (1, 4)$ (1, 3), (1, 4) і $(1, 5)$ будуть хорошими.

Нехай $i = 2$ i = 2. Шукаємо найменший індекс $j$ , такий що $c j > - c_{2} = 0$ cj > - c_2 = 0. Таким індексом буде $j = 3$ j = 3. Відповідно, пари індексів $(2, 3), (2, 4)$ (2, 3), (2, 4) і $(2, 5)$ будуть хорошими.

Нехай $i = 3$ i = 3. Шукаємо найменший індекс $j$ , такий що $c_{j} > - c_{3} = - 3$ c_j > - c_3 = -3. Таким індексом буде $j = 1$ j = 1. Пара $(i, k)$ буде хорошою, якщо виконуються дві умови: $k \geq j$ k \ge j і $k > i$ k > i. В цьому випадку хорошими є пари індексів $(3, 4)$ і $(3, 5)$ . Пари $(3, 1)$ і $(3, 2)$ також будуть хорошими, але вони вже були враховані раніше при розгляді $i = 1$ i = 1 (пара $(1, 3)$ ) і $i = 2$ i = 2 (пара $(2, 3)$ ).

Нехай $i = 4$ i = 4. Єдиною хорошою парою буде $(4, 5)$ .

Всього є $11$ пар хороших індексів.

Реалізація алгоритму

Читаємо вхідні дані.

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]);

Будуємо масив різниць $c$ , в якому $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];

Сортуємо масив $c$ за зростанням.

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

Кількість хороших пар індексів будемо підраховувати в змінній $r es$ .

res = 0;

Перебираємо індекси $i$ .

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

Для кожного індексу $i$ знаходимо мінімальний індекс $p os$ , такий що $c_{p os} > - c_{i}$ c_{pos} > - c_i. При цьому має виконуватися умова $p os \geq i + 1$ pos \ge i + 1.

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

Хорошими будуть всі пари індексів $(i, k)$ , для яких $p os \leq k \leq n - 1$ pos \le k \le n - 1. Кількість таких значень $k$ дорівнює $(n - 1) - p os + 1 = n - p os$ (n - 1) - pos + 1 = n - pos.

  res += n - pos;
}

Виводимо відповідь.

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