So, here is the solution, you store each element as you see in a map.
Every-time, for each element(say,โxโ) , before inserting it you apply lower-bound function on map for x+k and x-k; and it is solved
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int k;
map<int,int> mp;
int solve(int A[],int beg,int end1)
{
int count1=0;
if(beg==end1) return 0;
if(abs(A[end1]-A[beg])<=k){
auto it = mp.find(end1);
if(it==mp.end())
{
count1++; mp.insert({end1,beg});
}
else if(it->second!=beg){
count1++; mp.insert({end1,beg});
}
}
count1+= solve(A,beg+1,end1);
count1+= solve(A,beg,end1-1);
return count1;
}
int main()
{
int n;
cin>>n>>k;
int A[n];
for(int i=0;i<n;i++) cin>>A[i];
int t = solve(A,0,n-1);
cout<<t+n<<endl;
}
can you tell me this is correct or not?? i am not sure about large inputs.
@gagangaur Bro can please explain me how to apply sliding window concept here and if possible share the code it would help alot.
@anon55659401 bro can you please show some light on how you solved the second question using โTriesโ if possible.
your approach gets TLE as its complexity is O(nlogn +n^2), we need O(nlogn + n) approach
@anon55659401 bro can you please expain the solution a bit as i really want to learn its solution as previously i was not that much active in solving the contest problems which i was not able to solve during contest beacuse of which i was not able to grow as CP .
I was having endsem exam. Thats why no replyโฆ Waitโฆ Iโll explain you in detail