fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define    ll              long long int
  5. #define    ld              long double
  6. #define    rd(a)           cin>>a
  7. #define    pt(a)           cout<<a
  8. #define    pb              push_back
  9. #define    mp              make_pair
  10. #define    cl              endl
  11. #define    ifor(i,a,b)     for(i=a;i<=b;i++)
  12. #define    dfor(i,a,b)     for(i=a;i>=b;i--)
  13. #define    pii             pair<int,int>
  14. #define    sz              100000
  15. #define    mad             1000000007
  16.  
  17. ll tree[4*sz +5];
  18. ll a[sz+5],b[sz+5];
  19. ll n,s;
  20. vector<pair<ll,ll>> v;
  21.  
  22. ll maxi(ll a,ll b) {
  23.  
  24.     if(a>=b) return a;
  25.     else return b;
  26. }
  27. ll mini(ll a,ll b) {
  28.  
  29.     if(a>=b) return b;
  30.     else return a;
  31. }
  32.  
  33. ll query(ll node,ll s,ll e,ll l,ll r) {
  34.  
  35.     if(s>r || l>e) return 0;
  36.  
  37.     if(s>=l && e<=r) return tree[node];
  38.  
  39.     ll mid=(s+e)/2;
  40.  
  41.     ll p1=query(2*node,s,mid,l,r);
  42.     ll p2=query(2*node +1,mid+1,e,l,r);
  43.  
  44.     return max(p1,p2);
  45. }
  46.  
  47. void update(ll node,ll s,ll e,ll idx,ll val) {
  48.  
  49.     if(s==e) {
  50.  
  51.         //cout<<"node="<<node<<"\n";
  52.         tree[node]=val;
  53.     }
  54.     else {
  55.  
  56.         ll mid=(s+e)/2;
  57.  
  58.         if(s<=idx && idx<=mid) {
  59.             update(2*node,s,mid,idx,val);
  60.         }
  61.         else {
  62.             update(2*node +1,mid+1,e,idx,val);
  63.         }
  64.  
  65.         tree[node]=maxi(tree[2*node],tree[2*node +1]);
  66.     }
  67. }
  68.  
  69. ll f(ll k) {
  70.  
  71.     memset(tree,0,sizeof(ll)*(sz));
  72.     memset( b,0,sizeof(ll)*(sz+5));
  73.  
  74.     ll i,j;
  75.     ll p,q;
  76.     ll l,r;
  77.     for(i=1;i<=v.size()-1;i++) {
  78.  
  79.         j=i+1;
  80.         while(v[j].first==v[i].first) {
  81.             j++;
  82.         }
  83.         for(p=i;p<=j-1;p++) {
  84.  
  85.             l=maxi(1,v[p].second-k); r=mini(n,v[p].second+k);
  86.             b[p]=query(1,1,n,l,r) +1;
  87.         }
  88.  
  89.         for(p=i;p<=j-1;p++) {
  90.  
  91.             ll cm=b[p];
  92.             q=p+1;
  93.             while((v[q-1].second + k)>=(v[q].second) && q<=(j-1)) {
  94.                 cm=maxi(cm,b[q]);
  95.                 q++;
  96.             }
  97.  
  98.             for(int c=p;c<=(q-1);c++) {
  99.                 b[c]=cm;
  100.             }
  101.             p=q-1;
  102.         }
  103.         for(p=i;p<=j-1;p++) {
  104.  
  105.             update(1,1,n,v[p].second,b[p]);
  106.         }
  107.         i=j-1;
  108.     }
  109.  
  110.     ll sum=0;
  111.     for(i=1;i<=n;i++) {
  112.         sum=sum + b[i];
  113.     }
  114.     if(sum<=s) return 1;
  115.     else return 0;
  116. }
  117. int main() {
  118.  
  119.     ios_base::sync_with_stdio(0);
  120.     cin.tie(0);
  121.     cout.tie(0);
  122.  
  123.     int t;cin>>t;
  124.     ll i,j,k;
  125.  
  126.     while(t--) {
  127.  
  128.         cin>>n>>s;
  129.  
  130.         v.pb(mp(0,0));
  131.         for(i=1;i<=n;i++) {
  132.  
  133.             cin>>a[i];
  134.             v.pb(mp(a[i],i));
  135.         }
  136.         sort(v.begin(),v.end());
  137.  
  138.         ll low=0,high=n,ans=-1;
  139.  
  140.         while(low<=high) {
  141.  
  142.             ll mid=(low+high)/2;
  143.             if(f(mid)) {
  144.                 ans=mid;
  145.                 low=mid+1;
  146.             }
  147.             else {
  148.                 high=mid-1;
  149.             }
  150.         }
  151.         cout<<ans+1<<"\n";
  152.         v.clear();
  153.     }
  154. }
Success #stdin #stdout 0s 4428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TVXNPo
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 years 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!