fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define NMAX 100005
  3. #define ValMax 100000
  4. using namespace std;
  5. int n , k;
  6. int val[NMAX];
  7. int segment[4 * NMAX];
  8.  
  9. void update(int node , int l , int r , int pos , int length)
  10. {
  11.     if(pos < l || pos > r) return;
  12.  
  13.     if(l == r)
  14.     {
  15.         segment[node] = max(segment[node] , length);
  16.         return;
  17.     }
  18.  
  19.     int mid = (l + r)>> 1;
  20.  
  21.     update(2 * node , l , mid , pos , length);
  22.  
  23.     update(2 * node + 1 , mid + 1 , r , pos , length);
  24.  
  25.     segment[node] = max(segment[2 * node] , segment[2 * node + 1]);
  26. }
  27.  
  28. int GetPre(int node , int l , int r , int u , int v)
  29. {
  30.     if(u > r || v < l)  return 0;
  31.  
  32.     if(u <= l && r <= v)  return segment[node];
  33.  
  34.     int mid = ( l + r ) >> 1;
  35.  
  36.     return max(GetPre(2 * node , l , mid , u , v) , GetPre(2 * node + 1 , mid + 1 , r , u , v));
  37. }
  38.  
  39. void process()
  40. {
  41.     cin>> n >> k;
  42.  
  43.     for(int i = 1 ; i <= n ; i++)  cin>>val[i];
  44.  
  45.     for(int i = 1 ; i <= n ; i++)  
  46.     { 
  47.     	update(1 , 1 , ValMax , val[i] , GetPre(1 , 1 , ValMax , val[i] - k , val[i] - 1) + 1);
  48.     }
  49.  
  50.     cout<<GetPre(1 , 1 , ValMax , 1 , ValMax);
  51. }
  52. int main()
  53. {
  54.     ios_base::sync_with_stdio(0);
  55.     cin.tie(nullptr);
  56.     cout.tie(nullptr);
  57.     process();
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1mp0Ut
language:
C++14 (gcc 8.3)
created:
16 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!