fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int INF= 1e9+7;
  5. ll n,k,res,a[1000005],bit[1000005];
  6. // fenwick tree
  7. void update(ll x,ll val){
  8.     for(;x<=1000005;x+=x&-x) bit[x]=min(bit[x],val);
  9. }
  10. ll get(ll x){
  11.     ll res=INF;
  12.     for(;x>0;x-=x&-x) res=min(res,bit[x]);
  13.     return res;
  14. }
  15. int main(){
  16.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  17.     cin >> n >> k;
  18.     vector<ll> f(n+1,0);
  19.     for(int i=1;i<=n;++i) cin >> a[i],a[i]-=k;
  20.     for(int i=1;i<=n;++i) a[i]=f[i]=f[i-1]+a[i];
  21.     memset(bit,INF,sizeof(bit));
  22.     // nén giá trị
  23.     sort(f.begin()+1,f.end());
  24.     f.resize(unique(f.begin(),f.end())-f.begin());
  25.     for(int i=1;i<=n;++i) a[i]=lower_bound(f.begin()+1,f.end(),a[i])-f.begin()+1;
  26.     update(a[1],1);
  27.     for(ll i=2;i<=n;++i){
  28.         ll id=get(a[i]);
  29.         update(a[i],i);
  30.         res=max(res,i-id);
  31.     }
  32.     cout << res;
  33.     return 0;
  34. }
  35.  
Success #stdin #stdout 0.01s 11700KB
comments (?)
stdin
copy 
7 3
1 5 2 3 1 4 1
stdout
copy 
5
https://ideone.com/d2R6T5
language:
C++ (gcc 8.3)
created:
13 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!