The Canadian Computing Olympiad: the road from CCC Senior to the IOI

Sample input:
6 3
10 1 4 13 7 2

Sample output:
6

// Our practice task: Signal Towers, subtask 1 (N up to 2,000)
// Check every pair: about N * N / 2 comparisons.
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long d;
    cin >> n >> d;
    vector<long long> x(n);
    for (auto &v : x) cin >> v;
    long long pairs = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (llabs(x[i] - x[j]) <= d) pairs++;
    cout << pairs << "\n";
    return 0;
}

About two million comparisons when N is 2,000: well inside the time. At N = 200,000 it would need about twenty billion, far too many. This version earns the first 40 percent and nothing more, and that is a perfectly good start on contest day.

// Our practice task: Signal Towers, full solution (N up to 200,000)
// Sort, then slide a window: O(N log N) for the sort, O(N) after.
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long d;
    cin >> n >> d;
    vector<long long> x(n);
    for (auto &v : x) cin >> v;
    sort(x.begin(), x.end());
    long long pairs = 0;   // up to about 2 * 10^10: needs long long
    int left = 0;
    for (int right = 0; right < n; right++) {
        while (x[right] - x[left] > d) left++;
        pairs += right - left;   // towers left .. right-1 reach tower right
    }
    cout << pairs << "\n";
    return 0;
}

After sorting, the towers a given tower can reach on its left form one unbroken block, so a left pointer only ever moves forward. Each tower is added and removed from the window once: linear time after the sort. Our arithmetic on the count: if all 200,000 towers stood at one spot, there would be 200,000 x 199,999 / 2 = 19,999,900,000 pairs, far beyond the roughly 2.1 billion an int can hold, so the count is a long long.