fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/y5tsgk
language:
C++ (gcc 8.3)
created:
292 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!