fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <stdio.h>
  3.  
  4. #define __Shibae__      signed main()
  5. #define IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define fiopen(Path)    freopen(Path".INP", "r", stdin); freopen(Path".OUT", "w", stdout);
  7. #define fipen(Path)     freopen(Path".INP", "r", stdin);
  8. #define sz(s)           (int)s.size()
  9. #define all(x)          x.begin(), x.end()
  10. #define maxHeap         priority_queue<int>
  11. #define minHeap         priority_queue<int, vector<int>, greater<int>>
  12. #define getBit(x, k)    (((x) >> (k)) & 1)
  13. #define MASK(i)         (1LL << (i))
  14. #define SQR(x)          (1LL * ((x) * (x)))
  15. #define db              double
  16. #define ld              long double
  17. #define ui              unsigned int
  18. #define ll              long long
  19. #define ii              pair<int, int>
  20. #define pli             pair<ll, int>
  21. #define pil             pair<int, ll>
  22. #define pll             pair<ll, ll>
  23. #define fi              first
  24. #define se              second
  25.  
  26. #define FOR(i, a, b)    for(int i = a, _b = b; i <= _b; i += 1)
  27. #define FOD(i, a, b)    for(int i = a, _b = b; i >= _b; i -= 1)
  28. #define REP(i, a)       for(int i = 0, _a = a; i < _a; i++)
  29. #define pb              push_back
  30. #define fau(u, a)       for(auto &u : a)
  31.  
  32. using namespace std;
  33.  
  34. const ll mod = 1e9 + 7;
  35. const int INF = 1e9 + 7;
  36. const ll INFLL = (ll)2e18 + 7LL;
  37. const ld PI = acos(-1);
  38. const int MAX = 5e5+5;
  39.  
  40. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  41. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  42.  
  43. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  44.  
  45. ll Rand(ll l, ll r) 
  46. {
  47.     return l + rd() % (r - l + 1);
  48. }
  49.  
  50. template<class SHIBA, class ENGINE>
  51.     bool minimize(SHIBA &x, const ENGINE y)
  52.     {
  53.         if(x > y)
  54.         {
  55.             x = y;
  56.             return true;
  57.         } 
  58.         else return false;
  59.     }
  60. template<class SHIBA, class ENGINE>
  61.     bool maximize(SHIBA &x, const ENGINE y)
  62.     {
  63.         if(x < y)
  64.         {
  65.             x = y;
  66.             return true;
  67.         }
  68.         else return false;
  69.     }
  70.  
  71.  
  72. /* Template by: Nguyen Nhat Anh from Luong Van Chanh High School for the gifted */
  73. /* From Min Tuoi with love */
  74.         /**       TRY HARD        **/
  75.         /**          ORZ          **/
  76.  
  77. /* -----------------[ MAIN CODE ]----------------- */
  78.  
  79. int n, x;
  80. int a[MAX];
  81. vector<int> arr;
  82. int ff[MAX];
  83.  
  84. void input()
  85. {
  86.     cin >> n >> x;
  87.     FOR(i, 1, n)
  88.     {
  89.         cin >> a[i];
  90.         arr.pb(a[i]);
  91.         arr.pb(a[i] + x);
  92.     }
  93. }
  94.  
  95. struct SegmentTree
  96. {
  97.     int st[MAX << 2];
  98.     int n;
  99.  
  100.     void build(int _)
  101.     {
  102.         memset(st, 0, sizeof st);
  103.         n = _;
  104.     }
  105.  
  106.     void update(int p, int k)
  107.     {
  108.         p--;
  109.         for (maximize(st[p += n], k); p > 1; p >>= 1) maximize(st[p >> 1], max(st[p], st[p ^ 1]));
  110.     }
  111.  
  112.     int get(int l, int r)
  113.     {
  114.         l--;
  115.         int res = 0;
  116.         for (l += n, r += n; l < r; l >>= 1, r >>= 1)
  117.         {
  118.             if (l & 1) maximize(res, st[l++]);
  119.             if (r & 1) maximize(res, st[--r]);
  120.         }
  121.         return res;
  122.     }
  123. }st;
  124.  
  125. void solve()
  126. {
  127.     sort(all(arr));
  128.     arr.resize(unique(all(arr)) - arr.begin());
  129.     st.build(2*n);
  130.  
  131.     st.build(2*n);
  132.     int res = 1;
  133.  
  134.     FOD(i, n, 1)
  135.     {
  136.         int t = lower_bound(all(arr), a[i] + x) - arr.begin() + 1;
  137.         ff[i] = st.get(t+1, 2*n) + 1;
  138.         maximize(res, ff[i]);
  139.         st.update(t, ff[i]);
  140.     }
  141.  
  142.     st.build(2*n);
  143.  
  144.     FOR(i, 1, n)
  145.     {
  146.         int t = lower_bound(all(arr), a[i]) - arr.begin() + 1;
  147.         int tt = lower_bound(all(arr), a[i] + x) - arr.begin() + 1;
  148.  
  149.         maximize(res, st.get(1, tt-1) + ff[i]);
  150.  
  151.         st.update(t, st.get(1, t-1) + 1);
  152.     }
  153.     assert(*max_element(ff+1, ff+1+n) == st.get(1, 2*n));
  154.     cout << res;
  155. }
  156.  
  157. __Shibae__
  158. {
  159.     IOS
  160.     fipen("DAYDEP");
  161.  
  162.     const bool multitest = 0;
  163.     int tt = 1; if(multitest) cin >> tt;
  164.  
  165.     while( tt-- ){
  166.         input();
  167.         solve();
  168.     }
  169.  
  170.     return 0;
  171. }
Success #stdin #stdout 0.01s 13988KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/kMkKwY
language:
C++ (gcc 8.3)
created:
1 day 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!