Директор школы доверил провести линейку учителю математики, но тот воспринял это задание буквально и выстроил всех учеников школы в одну длинную линию. Увидев это директор решил…

Давайте разберем задачу шаг за шагом и приведем решение.

Задача:
У нас есть учеников, каждый ученик находится в определенной позиции x и принадлежит к определенному классу y. Все ученики выстроены в линию по их координате x. Нам нужно посчитать:

• Болтливость — сумму попарных расстояний между учениками одного класса.
• Задирчивость — сумму попарных расстояний между учениками разных классов.

Что нужно сделать:

1. Считать число классов K.
2. Считать число учеников N.
3. Для каждого ученика записать его позицию x и класс y.
4. Обработать учеников по классам, чтобы найти:
   • сумму попарных расстояний внутри каждого класса (болтливость).
   • сумму попарных расстояний между учениками разных классов (задирчивость).

Основные идеи:

• Болтливость (одинаковый класс):
  Для каждого класса нужно вычислить сумму попарных разностей. Можно упростить:
  Для множества учеников x1, x2, ..., x_m у каждого класса, сумма попарных расстояний равна:

  \[ \sum_{i<j} |x_j - x_i| \]

  Можно решить быстрее, отсортировав учеников этого класса по координате x. Тогда:

  \[ \sum_{i<j} (x_j - x_i) \] так как x_j >= x_i, и абсолютное значение пропадает.

  Формула для подсчета суммы попарных разностей после сортировки:

  Пусть отсортированные координаты: X = [x_1, x_2, ..., x_m]

  Тогда:

  \[ \text{Sum} = \sum_{i=1}^{m} x_i \cdot (i-1) - \sum_{i=1}^{m} x_i \cdot (m - i) \]

  Через префиксные суммы это можно сделать быстрее.

• Задирчивость (разные классы):
  Нужно найти сумму попарных расстояний между всеми учениками двух разных классов.
  Изначально можно подойти так:
  Посчитать сумму всех попарных расстояний между всеми учениками, а затем вычесть сумму внутри каждого класса (то есть сумму внутриодноклассных расстояний).
  Но это не очень просто, если не учитывать повторные подсчеты и большое количество учеников.

Эффективный подход:

1. Для каждого ученика запомним x и y.

2. Создадим два массива:

   • массив positions для подсчета внутри каждого класса.
   • массив all_positions для подсчета всех учеников в целом.

3. Для подсчета внутри класса:

   • Для каждого класса соберите все позиции учеников, отсортируйте их.
   • Посчитайте сумму попарных расстояний по формуле.

4. Для подсчета между классами:

   • Можно использовать следующую идею:
     • После подсчета всех учеников и сортировки, можно стремительно собрать сумму всех расстояний между всеми учениками (общая сумма), также используя префиксы.
     • Тогда за счет вычитания внутренне классовых расстояний получим сумму для заказанных наборов.

Но легче всего — использовать суммы:

• Объявим переменную total_sum — сумму расстояний между всеми учениками.
• Собрав всех учеников и отсортировав их по x, мы можем определить total_sum так:

\[ \text{total\_sum} = \sum_{i=1}^{N} (x_i \times (2i - N - 1)) \]

где (x_i, y_i) — отсортированные по x.

Затем:

• Для каждого класса посчитаем внутреннюю сумму (сумма внутри одного класса).
• Заменим сумму между разными классами:

\[ \text{разные\_классы} = \text{total\_sum} - \sum_{\text{класс}} \text{внутреннюю сумму класса} \]

Итоговая реализация:

• Читаем входные данные.
• Собираем для каждого класса список позиций x.
• Находим сумму попарных расстояний внутри класса.
• Считаем сумму всех попарных расстояний между всеми учениками.
• Вычисляем болтливость и задирчивость по формулам.

Код решения (на Python):

import sys
input = sys.stdin.read

def main():
    data = input().split()
    K = int(data[0])          # число классов
    N = int(data[1])          # число учеников
    students = []
    index = 2
    for _ in range(N):
        x = int(data[index])
        y = int(data[index + 1])
        students.append((x, y))
        index += 2

    # Собираем позиции по классам
    classes = [[] for _ in range(K + 1)]
    for x, y in students:
        classes[y].append(x)

    # Сортируем позиции внутри каждого класса
    for c in range(1, K + 1):
        classes[c].sort()

    # Функция для подсчета суммы попарных расстояний внутри одного массива
    def sum_of_pairwise_differences(arr):
        prefix_sum = 0
        result = 0
        for i, val in enumerate(arr):
            result += val * i - prefix_sum
            prefix_sum += val
        return result

    # Болтливость — сумма попарных расстояний внутри каждого класса
    boltivost = 0
    # Общая сумма попарных расстояний между всеми учениками
    # Для этого отсортируем всех учеников по x
    students_sorted = sorted(students, key=lambda c: c[0])
    all_x = [x for x, y in students_sorted]
    total_sum = 0
    prefix_sum = 0
    for i, x in enumerate(all_x):
        total_sum += x * i - prefix_sum
        prefix_sum += x

    # Подсчет суммы внутри каждого класса
    internal_sum = 0
    for c in range(1, K + 1):
        internal_sum += sum_of_pairwise_differences(classes[c])

    # Болтливость — сумма внутри класса
    boltivost = internal_sum

    # Задирчивость — сумма между всеми учениками минус сумма внутри классов
    zadirchivost = total_sum - internal_sum

    print(boltivost)
    print(zadirchivost)

if __name__ == "__main__":
    main()

Итоги:

• Вывод — это два числа:
  • Болтливость (сумма попарных расстояний внутри классов).
  • Задирчивость (сумма попарных расстояний между учениками разных классов).

Если хотите, я могу помочь еще подробнее объяснить каждую часть или адаптировать решение под конкретные требования.