fork download
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define endl "\n"
  4. #define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
  5. using namespace std;
  6. // #include <ext/pb_ds/assoc_container.hpp>
  7. // #include <ext/pb_ds/tree_policy.hpp>
  8. // using namespace __gnu_pbds;
  9. // #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  10. //less_equal to ordered multiset
  11. class SegmentTree {
  12. private:
  13. vector<int> tree;
  14. vector<int> arr;
  15. int n;
  16.  
  17. // Build the segment tree recursively
  18. void build(int node, int start, int end)
  19. {
  20. if (start == end)
  21. {
  22. tree[node] = arr[start];
  23. }
  24. else
  25. {
  26. int mid = (start + end) / 2;
  27. build(2 * node + 1, start, mid);
  28. build(2 * node + 2, mid + 1, end);
  29. tree[node] = max(tree[2 * node + 1] , tree[2 * node + 2]);
  30. }
  31. }
  32.  
  33. // Update the value at index 'idx' to 'val' recursively
  34. void update(int node, int start, int end, int idx, int val) {
  35. if (start == end)
  36. {
  37. arr[idx] = val;
  38. tree[node] = val;
  39. }
  40. else
  41. {
  42. int mid = (start + end) / 2;
  43. if (idx >= start && idx <= mid)
  44. {
  45. update(2 * node + 1, start, mid, idx, val);
  46. }
  47. else
  48. {
  49. update(2 * node + 2, mid + 1, end, idx, val);
  50. }
  51. tree[node] = max(tree[2 * node + 1] , tree[2 * node + 2]);
  52. }
  53. }
  54.  
  55. // Query the sum in the range [l, r] recursively
  56. int query(int node, int start, int end, int l, int r)
  57. {
  58. if(r < start || l > end)
  59. {
  60. return 0; // Out of range
  61. }
  62. if(l <= start && r >= end)
  63. {
  64. return tree[node]; // Current segment is fully within the query range
  65. }
  66. int mid = (start + end) / 2;
  67. int left = query(2 * node + 1, start, mid, l, r);
  68. int right = query(2 * node + 2, mid + 1, end, l, r);
  69. return max(left , right);
  70. }
  71.  
  72. public:
  73. // Constructor to initialize the segment tree with an array
  74. SegmentTree(vector<int>& input)
  75. {
  76. n = input.size();
  77. arr = input;
  78. tree.resize(4 * n); // Assuming a maximum size for the tree
  79. build(0, 0, n - 1);
  80. }
  81.  
  82. // Update the value at index 'idx' to 'val'
  83. void update(int idx, int val)
  84. {
  85. update(0, 0, n - 1, idx, val);
  86. }
  87.  
  88. // Query the sum in the range [l, r]
  89. int query(int l, int r)
  90. {
  91. return query(0, 0, n - 1, l, r);
  92. }
  93. };
  94.  
  95. void solve()
  96. {
  97. int n,d;
  98. cin>>n>>d;
  99. const int N=5e5+10;
  100. vector<int> v(n);
  101. vector<int> dp(N+5,0);
  102. for(int i=0;i<n;i++)
  103. {
  104. cin>>v[i];
  105. }
  106. SegmentTree st(dp);
  107. int ans=0;
  108. for(int i=0;i<n;i++)
  109. {
  110. int lb=max(0LL,v[i]-d),ub=min(N,v[i]+d);
  111. int mx=st.query(lb,ub);
  112. dp[v[i]]=max(dp[v[i]],mx+1);
  113. st.update(v[i],dp[v[i]]);
  114. ans=max(ans,dp[v[i]]);
  115. }
  116. cout<<ans<<endl;
  117. }
  118.  
  119. signed main(){
  120. FastIO;
  121. // #ifndef ONLINE_JUDGE
  122. // freopen("input.txt", "r", stdin);
  123. // freopen("output.txt", "w", stdout);
  124. // #endif
  125. int t=1;
  126. // cin>>t;
  127. for(int i=1;i<=t;i++)
  128. {
  129. //cout<<"Case #"<<i<<": ";
  130. solve();
  131. }
  132. return 0;
  133. }
Success #stdin #stdout 0.01s 26640KB
stdin
Standard input is empty
stdout
0