Distant Pairs
National Olympiad — Municipal round (2020 season)
Submission name: red.cpp
Problem summary
Count pairs i < j in a nondecreasing sequence for which A[j] − A[i] > R.
Input
N and R, then N sequence elements.
Output
The number of qualifying pairs.
Constraints
2 ≤ N ≤ 300000; 1 ≤ R, A[i] ≤ 10^9; A is nondecreasing.
Worked example
An independently prepared example for this explanation.
Input
4 4 1 3 5 8
Output
2
Solution analysis
- The sorted order makes the valid left endpoints a prefix for every right endpoint. Maintain left, the first position whose difference from the current element is at most R.
- While A[right] − A[left] > R, move left forward. Exactly left earlier positions have a difference greater than R, so add left to the answer. Both pointers only move forward.
- For 1, 3, 5, 8 with R = 4, the first three right endpoints contribute zero. At 8, the left pointer passes 1 and 3, giving the two pairs (1,8) and (3,8).
Why it works
After the while loop, every index below left satisfies the strict inequality and every index from left to right does not, by sorted order. Adding left counts precisely all valid pairs ending at right. Each pair has one right endpoint and is counted once.
Complexity: O(N) time because each pointer advances at most N times; O(N) space for the input.
Watch out. Use > R rather than ≥ R, and a 64-bit answer: there can be almost N(N−1)/2 pairs.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long threshold;
cin>>n>>threshold;
vector<long long>values(n);
for(auto&value:values){
cin>>value;
}
int left=0;
long long answer=0;
for(int right=0;right<n;++right){
while(values[right]-values[left]>threshold){
++left;
}
// All positions before left form a valid pair with right.
answer+=left;
}
cout<<answer<<'\n';
}