TLE in 5 sub-tasks

help
1

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)

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
3

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

4

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';
}