greedy_sort.cpp

// Greedy Algorithm

// 排序 + 雙指針 / HashMap — O(N log N)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

    int n;
    long long C;

    // Read input until EOF
    while (cin >> n >> C) {

        vector<long long> a((size_t)n);
        for (size_t i = 0; i < (size_t)n; i++) {
            cin >> a[i];
        }

        // Step 1: copy the array and sort it.
        vector<long long> sorted_a = a;
        sort(sorted_a.begin(), sorted_a.end());

        // Step 2: use two pointers to find the number of pairs (i, j) such that a[i] - a[j] == C
        long long ans = 0;
        for (size_t j = 0; j < (size_t)n; j++) {
            long long target = sorted_a[j] + C;

            // lower_bound: find the first element in sorted_a that is less than or equal to target
            // upper_bound: find the first element in sorted_a that is greater than target
            auto lo = lower_bound(sorted_a.begin(), sorted_a.end(), target);
            auto hi = upper_bound(sorted_a.begin(), sorted_a.end(), target);

            ans += hi - lo;
        }
        
        cout << ans << endl;
    }
    return 0;
}