TACHSTCK - Editorial

If L[1] = 1, L[2] = 3, L[n] = 2, L[m] = 5 and D= 2
so (L[1],L[2]) <= D
(L[1],L[n]) <= D
(L[2],L[m]) <= D
but (L[n],L[m]) > D

In this your second justification point fails.

https://www.codechef.com/viewsolution/29141752

what is wrong with this…

May be you have to start the for loop from 2 ??

https://www.codechef.com/viewsolution/37399668
please help me I am getting runtime error don’t know why???

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int main()
{
int n;
int con = 0;
ll d;
cin >> n >> d;
vector v;
set s;
map<ll, ll> m;
for(int i = 0; i < n; i++)
{
ll x; cin >> x;
v.push_back(x);
s.insert(x);
m[x]++;
}
sort(v.begin(), v.end());
for(int i = 0; i < v.size(); i++)
{
m[v[i]]–;
auto it = s.find(v[i]);
if( it != s.end())
{
if(m[v[i]] == 0)
s.erase(v[i]);
it = upper_bound( s.begin(), s.end(), v[i]+d);
if( it != s.begin()) it–;
if( abs(v[i]-*it) <= d)
{
con++;
m[*it]–;
if(m[*it] == 0)
s.erase(*it);
}
}
}
cout << con << endl;
}

/// what happened in my code, it’s getting wrong…
4 1
1 2 121 121
my output = 2
correct output = 2;

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,d,i;
ll count = 0;
cin >> n >> d;
ll a[n];
for(i = 0; i< n; i++){
cin >> a[i];
}
sort(a,a+n);
for(i = n-1; i>0; i–){
if((a[i] - a[i-1] != 0) && (a[i] - a[i-1] <= d)){
count ++;
}
else{
continue;
}
}
cout << count << endl;
}
WHATS WRONG WITH THIS CODE?

#include
using namespace std;

int main() {
int n,d;
cin>>n>>d;
int l[n];
for(int i=0; i<n; i++)
cin>>l[i];
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(l[j]<l[i])
{
int tmp=l[i];
l[i]=l[j];
l[j]=tmp;
}
}
}
int cnt=0;
for(int i=0; i<(n-1); i++)
{
if((l[i+1]-l[i])<=d)
{
cnt++;
i++;
continue;
}
}
cout<<cnt<<endl;
return 0;
}
Can anyone tell me why it is showing TLE -??

I think you should iterate from i=0 to n-1 , as if you will iterate from i=0 to n , then when i would be n-1 , i+1 would exceed the range.

I think you are running a o(n^2) approach but as N=1e5 , it will eventually exceed the time limit.