fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. const int N = 3e6;
  3. const int M = 1e6;
  4. #define ll long long
  5. const ll MOD = 1e9 + 1;
  6. const ll INF = 1e15;
  7. const ll base = 32;
  8. #define fi first
  9. #define se second
  10. using namespace std;
  11.  
  12. ll n, t;
  13. ll a[N+3];
  14. deque<ll> ma, mi;
  15.  
  16. int main(){
  17.     ios_base::sync_with_stdio(0);
  18.     cin.tie(0);
  19.     // freopen("main.inp","r",stdin);
  20.     // freopen("main.out","w",stdout);
  21.     cin>>n>>t;
  22.     for(int i=1;i<=n;i++)cin>>a[i];
  23.     int l = 1, r = n, ans = 0;
  24.     while(l <= r){
  25.         int mid = l + r >> 1;
  26.         ll res = 0, cnt = 0;
  27.         while(!ma.empty())ma.pop_back();
  28.         while(!mi.empty())mi.pop_back();
  29.         // cout<<mid<<"\n";
  30.         for(int i=1;i<mid;i++){
  31.             while(!ma.empty() and a[ma.back()] <= a[i])ma.pop_back();
  32.             ma.push_back(i);
  33.         }
  34.         for(int i=1;i<mid;i++){
  35.             while(!mi.empty() and a[mi.back()] >= a[i])mi.pop_back();
  36.             mi.push_back(i);
  37.         }
  38.         for(int i=mid;i<=n;i++){
  39.             while(!ma.empty() and a[ma.back()] <= a[i])ma.pop_back();
  40.             ma.push_back(i);
  41.             if(ma.front() <= i - mid)ma.pop_front();
  42.  
  43.             while(!mi.empty() and a[mi.back()] >= a[i])mi.pop_back();
  44.             mi.push_back(i);
  45.             if(mi.front() <= i - mid)mi.pop_front();
  46.             // cout<<a[ma.front()]<<" "<<a[mi.front()]<<"\n";
  47.             res = abs(a[ma.front()] - a[mi.front()]);
  48.             if(res <= t){
  49.                 cnt++;
  50.                 break;
  51.             }
  52.         }
  53.         if(cnt > 0){
  54.             ans = mid;
  55.             l = mid + 1;
  56.         }
  57.         else r = mid - 1;
  58.     }
  59.     cout<<ans<<"\n";
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/UJzDLt
language:
C++14 (gcc 8.3)
created:
12 days 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!