Một bài sử dụng multiset hay

Đề bài:

Given an array $A$ of size $N$, you can jump from an index $i$ to another index $j$ if $A[j]-A[i]$ >= $K$, for $j$ > $i$. Find the length of the longest sequence of jumps that can be possible in the array. You can start at any index.
Input Format:
First line contains an integer $K$.
Second line contains the integer $N$.
Third line contains $N$ space separated integers (The array $A$)
Output Format:
Print the required length.
Constrains:
$1$ ≤ $N,A[i],K$ ≤ $10$ ^$6$

SAMPLE INPUT

 

2 
7
1 3 1 4 5 7 10

SAMPLE OUTPUT

 

5

Explanation

1 3 5 7 10 - Length 5

Lời giải:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define MAX5 1000005
int arr[MAX5];
int n,k;
int dp[MAX5];
int n2(){
   int ans=0;
   for(int i=0;i<n;i++) dp[i]=1;
   for(int i=1;i<n;i++){
       for(int j=0;j<i;j++){
        if(arr[i]>=arr[j]+k){
            dp[i]=max(dp[i],1+dp[j]);
        }
       }
   }
   for(int i=0;i<n;i++){
      ans=max(ans,dp[i]);
   }
   return ans;
}
multiset<int> p;
multiset<int>:: iterator it;
int nlogn(){
    p.clear();
    for(int i=0;i<n;i++){
        int tmp=arr[i];
        it= p.upper_bound(tmp-k);
        if(it==p.end()){
            p.insert(tmp);
            continue;
        }
        if(*it>tmp){
            p.erase(it);
            p.insert(tmp);
        }
    }
    return p.size();
}
int main(){
   cin>>k>>n;
   for(int i=0;i<n;i++){
    cin>>arr[i];
   }
   cout<<nlogn()<<endl;
   return 0;
}