I was doing ZCO15002

My Solution : https://www.codechef.com/viewsolution/36075120

I got TLE in 5 sub-tasks
Can someone tell me a better solution? Mine is O(n^2)

Sort all elements and for each element binary search for the first index which has a value greater than or equal to a[i]+k. All positions from this position to the nth position can be paired with our index i.

This would make your complexity O(nlogn)

4 Likes

Can refer to my AC solution:
https://www.codechef.com/viewsolution/36078817

I used 2 pointers for this.

Complexity is \mathcal{O}(n \log{n}) due to sorting.

#include <bits/stdc++.h>

using namespace std;

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n, k;
cin >> n >> k;
vector <long long> v(n);
for (long long i = 0; i < n; ++i)
{
cin >> v[i];
}
sort(v.begin(), v.end());
long long i = 0, j = 0, count = 0;
while (i < n)
{
if (i > j)
j = i;
else if (j >= n)
break;
if (v[j] - v[i] >= k)
{
++i;
count += (n-j);
} else
++j;
}
cout << count << '\n';
}