Advertisement
Guest User

Untitled

a guest
Mar 31st, 2020
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ull unsigned long long
  5. #define endl '\n'
  6. #define ll int
  7. const int N = 3e5 + 5;
  8. ll dpx[N][20], dpn[N][20], f[N], a[N];
  9. int main(){
  10.         ios_base::sync_with_stdio(false);
  11.         cin.tie(0);
  12.         cout.tie(0);
  13.         //freopen("haircut.in", "r", stdin);
  14.         //freopen("haircut.out", "w", stdout);
  15.         ll n, k;
  16.         cin >> n >> k;
  17.         for (int i = 1; i <= n; i++) cin >> a[i];
  18.         for (int i = 1; i <= n; i++) {
  19.                 dpn[i][0] = a[i];
  20.                 dpx[i][0] = a[i];
  21.         }
  22.         for (int j = 1; j < 20; j++){
  23.                 for (int i = 1; (i + (1ll << j) - 1) <= n; i++){
  24.                         dpx[i][j] = max(dpx[i][j - 1], dpx[i + (1ll << (j - 1))][j - 1]);
  25.                         dpn[i][j] = min(dpn[i][j - 1], dpx[i + (1ll << (j - 1))][j - 1]);
  26.                 }
  27.         }
  28.         f[0] = 0;
  29.         ll ans = 0;
  30.         for (int i = 1; i <= n; i++){
  31.                 ll l = 1, h = i;
  32.                 while (l <= h){
  33.                         ll mid = (l + h) >> 1;
  34.                         ll j = (ll)(log2(i - mid + 1));
  35.                         ll minimum = min(dpn[mid][j], dpn[i - (1ll << j) + 1][j]);
  36.                         ll maximum = max(dpx[mid][j], dpx[i - (1ll << j) + 1][j]);
  37.                         ll ok = maximum - minimum;
  38.                         if (ok > k) l = mid + 1;
  39.                         else h = mid - 1;
  40.                 }
  41.                 f[i] = max(f[i - 1], i - l + 1);
  42.                 ans = max(ans, i - l + 1 + f[l - 1]);
  43.         }
  44.         cout << ans;
  45. }
  46. /*
  47. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement