fork download
copy 
  1. // SIGMA BOY hihihihihihihi
  2.  
  3. #define se second
  4. #define fi first
  5. #define pb push_back
  6. #define pob pop_back
  7. #define bitebi __builtin_popcountll
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std ;
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef pair<ll,ll> pll;
  14.  
  15. const ll Mod = 1e9+7;
  16. const ll Maxn = 1e5+1;
  17. const int oo = 1e9;
  18.  
  19. ll n , k , a[Maxn],m,Before[Maxn],st[Maxn*4],dp[Maxn];
  20. pair<ll,ll> idrl[Maxn];
  21. vector<ll> v;
  22. unordered_map<ll,ll> id;
  23.  
  24. void Nen()
  25. {
  26.     sort(v.begin(),v.end());
  27.     v.erase(unique(v.begin(),v.end()),v.end());
  28.     for ( int i = 0 ; i < v.size() ; ++i)
  29.         id[v[i]]=i;
  30.  
  31.     m = v.size();
  32.     for ( int i = 0 ; i < v.size() ; ++i)
  33.     {
  34.         idrl[i].fi = upper_bound(v.begin(),v.end(),v[i]-k) - v.begin() - 1 ;
  35.         idrl[i].se = lower_bound(v.begin(),v.end(),v[i]+k) - v.begin() ;
  36.         //cerr << i << ' ' << v[i] << ' ' << idrl[i].fi << ' ' << idrl[i].se << '\n';
  37.     }
  38. }
  39.  
  40. void Update ( int id , int l , int r , int location , ll val )
  41. {
  42.     if(location<l||location>r) return;
  43.     if(l==r)
  44.     {
  45.         st[id] = max(st[id],val);
  46.         return;
  47.     }
  48.     int mid = (l+r)/2;
  49.     Update(id*2,l,mid,location,val);
  50.     Update(id*2+1,mid+1,r,location,val);
  51.     st[id] = max(st[id*2],st[id*2+1]);
  52. }
  53.  
  54. int Get ( int id , int l , int r , int u , int v )
  55. // Return Max Buoc
  56. {
  57.     if(r<u||v<l) return -oo;
  58.     if(u<=l&&r<=v) return st[id];
  59.     int mid = (l+r)/2;
  60.     return max(Get(id*2,l,mid,u,v),Get(id*2+1,mid+1,r,u,v));
  61. }
  62.  
  63. void DP()
  64. {
  65.     for (int i = 1 ; i <= n ; ++i)
  66.     {
  67.         int ID = id[a[i]];
  68.         int val = 0 ;
  69.         if(idrl[ID].fi>=0) val = max(val,Get(1,0,m-1,0,idrl[ID].fi));
  70.         if(idrl[ID].se<m) val = max(val,Get(1,0,m-1,idrl[ID].se,m-1));
  71.         dp[i] = val + 1;
  72.         Update(1,0,m-1,ID,dp[i]);
  73.     }
  74. }
  75.  
  76. void Print()
  77. {
  78.     cout << *max_element(dp+1,dp+1+n) << '\n';
  79.     int idEnd = max_element(dp+1,dp+1+n) - dp;
  80.     //for (int i = 1 ; i <= n ; ++i) cerr << dp[i] << ' ' ;
  81.     vector<int> v;
  82.     while(idEnd)
  83.     {
  84.         v.pb(idEnd);
  85.         int IDcur = idEnd;
  86.         while(idEnd)
  87.         {
  88.             if(abs(a[idEnd]-a[IDcur])>=k&&dp[IDcur]==dp[idEnd]+1) break;
  89.             idEnd--;
  90.         }
  91.     }
  92.  
  93.     reverse(v.begin(),v.end());
  94.     for ( auto x : v ) cout << x << ' ' ;
  95. }
  96.  
  97. void Do()
  98. {
  99.     cin >> n >> k ;
  100.     for (int i = 1 ; i <= n ; ++i)
  101.     {
  102.         cin >> a[i];
  103.         v.pb(a[i]);
  104.     }
  105.     Nen();
  106.     DP();
  107.     Print();
  108. }
  109.  
  110. signed main ()
  111. {
  112.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  113. #define task "test"
  114.     if(fopen(task".inp", "r")){
  115.         freopen(task".inp", "r", stdin);
  116.         freopen(task".out", "w", stdout);
  117.     }
  118.     int ntest=1;
  119.     while(ntest--) Do();
  120.  
  121.     cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
  122. }
Success #stdin #stdout #stderr 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
1
stderr
copy 
Time elapsed: 7ms
https://ideone.com/0QAHkE
language:
C++14 (gcc 8.3)
created:
3 hours ago
visibility:
public

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!