hypershashki.cpp

/*
Гипершашки.

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гепершашки участвует три игрока.
По ходу игры каждый из игроков набирает некоторое положительное целое число баллов.
Если после окончания игры первый игрок набрал a баллов, второй - b, третий c, то говорят, что игра закончилась со счетом a:b:c.
Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в k раз.
После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа
x1, x2, ..., xn. Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.
Требуется написать программу, которая по числу k и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.

Формат ввода
Первая строка содержит два целых числа: n и k (3 <= n <= 100000, 1 <= k <= 10^9).
Вторая строка содержит n целых чисел x1, x2, ..., xn (1 <= xi <= 10^9).

Формат вывода
Одно целое число - искомое количество различных вариантов счета.

Примеры
3 1
1 1 1

1


6 6
1 1 1 2 2 2

8


6 3
1 2 3 4 5 6

66


3 1
1 2 3

0


5 2
2 2 3 4 5

18

*/

#include <iostream>
#include <vector>
#include <algorithm>

/*
Подсчёт комбинаций.
Тройки вида a b c:
    Нужно знать сколько УНИКАЛЬНЫХ чисел в отрезке N = N([a + 1; a * k]) => += N * (N - 1) * 3 это всех три различные числа

Тройки вида a b b, b a b, b b a:
    Нужно знать число дублей (или больше) это D = D([a + 1; a * k]). => += D * 3

Тройки вида a a b, a b a, b a a:
    Если a сама является дублем, то прибавляем количество уникальных чисел и умножаем на 3. .

Тройки вида a a a:
    К общему числу комбинаций надо добавить количество тройных карточек += T(по всем X, где колич >= 3)

5 3
1 2 3 4 5
30

1 2 3
2 3 4
2 3 5
2 4 5
3 4 5

*/

int main()
{
    unsigned long long n, k;
    std::cin >> n >> k;

    std::vector<unsigned long long> x(n);

    //for (unsigned long long i = 0; i < n; i++)
    //    x[i] = i + 1;

    for (int i = 0; i < n; i++)
        std::cin >> x[i];

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

    // Обрабатываем первое число
    unsigned long long l = 1;
    for (; l < n && x[l] == x[l - 1]; l++);
    // l указывает на следующее уникальное число после первого

    unsigned long long count = 0;
    for (unsigned long long number = x[0], unique = 0, doubles = 0, r = l, counta = l; l < n;) {
        // Обрабатываем предыдущее число number

        // Считаем число уникальных чисел и дублей на отрезке [number + 1; number * k]
        unsigned long long upper_limit = number * k;
        for (; r < n && x[r] <= upper_limit; r++) {
            if (x[r] != x[r - 1]) {
                unique++;
            }
            else if (x[r] != x[r - 2]) {
                doubles++;
            }
        }


        // Тройки вида a b c
        count += unique * (unique - 1) * 3;

        // Тройки вида a b b, b a b, b b a
        count += doubles * 3;

        // Тройки вида a a b, a b a, b a a
        if (counta >= 2) {
            count += unique * 3;

            // Если a является триплетом
            if (counta >= 3) {
                count++;
            }

        }

        // Сдвигаемся на следующее число
        number = x[l];
        for (l++, counta = 1; l < n && x[l] == x[l - 1]; l++, counta++);

        // Если следующее число дубль, то исключаем его из числа дублей (т.к. интересуют только дубли ПОСЛЕ number)
        if (counta >= 2) {
            doubles--;
        }
        unique--;
    }

    // Если последняя комбинация была триплетом
    if (x[n - 1] == x[n - 2] && x[n - 1] == x[n - 3]) {
        count++;
    }

    std::cout << count << std::endl;
}